社区讨论

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 条回复,欢迎继续交流。

正在加载回复...