SPFA求条
查看原帖
SPFA求条
1271781
zhangchenyi_awa楼主2025/8/4 17:00

看老半天也没看出来哪错了

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
int a, b, c;
queue<int> q;
int dist[2010];
bool vis[2010];
struct ndoe {
    int to, next, wt;
} e[2010];
int tot;
int head[2010];
void add(int u, int v, int w) {
    tot++;
    e[tot].to = v;
    e[tot].wt = w;
    e[tot].next = head[u];
    head[u] = tot;
    return;
}
void SPFA(int s) {
    for(int i=1;i<=2000;i++){
        dist[i]=10000000000000;
    }
    memset(vis, false, sizeof(vis));
    dist[s] = 0;
    q.push(s);
    vis[s] = true;
    while (q.size() > 0) {
        int x = q.front();
        q.pop();
        vis[x] = false;
        for (int i = head[x]; i; i = e[i].next) {
            int y = e[i].to;
            if (dist[x] + e[i].wt < dist[y]) {
                dist[y] = min(dist[y],dist[x] + e[i].wt);
                if (!vis[y]) {
                    q.push(y);
                    vis[y] = true;
                }
            }
        }
    }
    return;
}
signed main() {
    scanf("%lld%lld",&n,&m);
    for (int i = 1; i <= m; i++) {
        scanf("%lld%lld%lld",&a,&b,&c);
        add(a, b, c);
    }
    SPFA(1);
    for(int i=1;i<=n;i++){
    	if(dist[i]!=10000000000000){
    		printf("%lld ",dist[i]);
		}else{
			printf("%lld ",-1);
		}
	}
    return 0;
}

悬关

2025/8/4 17:00
加载中...