社区讨论
WA第14个点,求助
P4878[USACO05DEC] Layout G参与者 3已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @locjg96k
- 此快照首次捕获于
- 2023/10/30 14:48 2 年前
- 此快照最后确认于
- 2023/11/05 02:06 2 年前
代码:
CPP#include <bits/stdc++.h>
#define add(z, zz, zzz) e[++len].to = zz, e[len].cost = zzz, e[len].next = el[z], el[z] = len
using namespace std;
struct edge {
int to, cost, next;
} e[200005];
int dis[50005], vis[50005], cnt[50005], el[200005];
queue<int> q;
int n, m, a, b, c, len, x, y;
int spfa(int x) {
memset(dis, 127, sizeof(dis));
memset(vis, 0, sizeof(vis));
memset(cnt, 0, sizeof(cnt));
dis[x] = 0, vis[x] = cnt[x] = 1, q.push(x);
while (q.size()) {
int x = q.front();
q.pop();
vis[x] = 0;
for (int i = el[x]; i; i = e[i].next) {
int y = e[i].to;
if (dis[y] > dis[x] + e[i].cost) {
dis[y] = dis[x] + e[i].cost;
cnt[y] = cnt[x] + 1;
if (cnt[y] > n) return 0;
if (!vis[y]) {
q.push(y), vis[y] = 1;
}
}
}
}
return 1;
}
int main() {
cin >> n >> x >> y;
for (int i = 0; i < x; ++i) scanf("%d%d%d", &a, &b, &c), add(a, b, c);
for (int i = 0; i < y; ++i) scanf("%d%d%d", &a, &b, &c), add(b, a, -c);
for (int i = 1; i <= n; ++i) add(0, i, 0);
if (!spfa(0) || !spfa(1))
puts("-1");
else if (dis[n] == 2139062143)
puts("-2");
else
cout << dis[n];
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...