思路：差分约束模板题，注意使用SPFA来判断负环，也即无解的情况。
#include<queue> #include<vector> #include<string> #include<math.h> #include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; #define maxn 5005 #define ll long long int n,m,dis[maxn],cnt[maxn]; bool vis[maxn]; queue<int> que; struct node{ int to,val; node(int to,int val):to(to),val(val){} }; vector<node> q[maxn]; bool SPFA(int start,int n){ memset(dis,127,sizeof(dis)); dis[start]=0; que.push(start); while(!que.empty()){ int now=que.front(); que.pop(); if(cnt[now]==n) return false; vis[now]=false; for(int i=0;i<q[now].size();i++){ int v=q[now][i].to; if(dis[v]>dis[now]+q[now][i].val){ dis[v]=dis[now]+q[now][i].val; if(!vis[v]){ vis[v]=true; que.push(v); cnt[v]++; } } } } return true; } int main(void){ int x,y,w; scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ scanf("%d%d%d",&x,&y,&w); q[y].push_back(node(x,w)); } for(int i=1;i<=n;i++) q[0].push_back(node(i,0)); if(SPFA(0,n)){ for(int i=1;i<n;i++) printf("%d ",dis[i]); printf("%d\n",dis[n]); } else printf("NO\n"); return 0; }
