一个题目的图的规模很大，并且变得权值全部为负数，那么他很可能设置了不利于spfa的测试数据，此时应该用更为稳定的dijkstra算法
#include<iostream> #include<algorithm> #include<cstring> #include<queue> #include<vector> using namespace std ; const long long INF = 0x3f3f3f3f3f3f3f3fLL ; const int N = 5e3 + 10 ; struct edge{ int to ; long long w ; edge(int too , long long ww){ to = too , w = ww ; } }; int n , m , s ; long long dis[N] ; vector<edge> e[N] ; bool inq[N] ; void spfa(int s){ memset(dis,0x3f,sizeof(dis)) ; dis[s] = 0 ; queue<int> q ; q.push(s) ; inq[s] = 1 ; while(!q.empty()){ int u = q.front() ; q.pop() ; inq[u] = 0 ; if(dis[u] == INF) continue ; for(int i = 0 ; i < e[u].size() ; i ++){ int v = e[u][i].to ; long long w= e[u][i].w; if(dis[v] > dis[u] + w){ dis[v] = dis[u] + w ; if(inq[v] == 0){ q.push(v) ; inq[v] = 1 ; } } } } } int main(){ cin >> n >> m >> s ; for(int i = 1 ; i <= m ; i ++){ int a , b ; long long c ; cin >> a >> b >> c ; e[a].push_back({b,c}) ; //e[b].push_back({a,c}) ; } spfa(s) ; for(int i = 1 ; i <= n ;i ++){ if(dis[i] == INF) cout << "-1 " ; else printf("%lld ", dis[i]) ; } }
