题意
给你一个图，问从源点到每个节点的最短路径分别是多少。 如果存在负权回路，只输出一行 -1；如果不存在负权回路，再求出一个点 S 到每个点的最短路的长度。如果 S 与这个点不连通，则输出NoPath。
思路
当然食用spfa啦。 先跑一下非源点的。万一数据卡你其他有环呢？ 然后再跑一次源点。得出Ans|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 |
#include<algorithm> #include<bitset> #include<complex> #include<deque> #include<exception> #include<fstream> #include<functional> #include<iomanip> #include<ios> #include<iosfwd> #include<iostream> #include<istream> #include<iterator> #include<limits> #include<list> #include<locale> #include<map> #include<memory> #include<new> #include<numeric> #include<ostream> #include<queue> #include<set> #include<sstream> #include<stack> #include<stdexcept> #include<streambuf> #include<string> #include<typeinfo> #include<utility> #include<valarray> #include<vector> #include<cctype> #include<cerrno> #include<cfloat> #include<ciso646> #include<climits> #include<clocale> #include<cmath> #include<csetjmp> #include<csignal> #include<cstdarg> #include<cstddef> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #define E 2000010 #define eps 1e-10 #define ll long long using namespace std; inline ll read(){ ll res=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar(); return res*f; } inline void write(ll x){ if(x<0) putchar('-'),x=-x; if(x<10) putchar(x+'0'); else{ write(x/10); putchar(x%10+'0'); } } //queue<ll> q; //set<ll> s; //priority_queue<ll> q1; //priority_queue<ll,vector<ll>,greater<ll> > q2; //list<ll> l; //stack<ll> s; ll n,m; ll fir[E],nxt[E],son[E],tot; double w[E],Max; void add(ll x,ll y,double z){++tot;nxt[tot]=fir[x];son[tot]=y;fir[x]=tot;w[tot]=z;} double dis[E],flag; ll vis[E]; queue<int> q; int tt[E]; ll spfa(ll s){ vis[s]=1; q.push(s); while(!q.empty()){ int u=q.front();q.pop(); for(ll i=fir[u];i;i=nxt[i]){ ll to=son[i]; if(dis[u]+w[i]<dis[to]){ dis[to]=dis[u]+w[i]; tt[to]++; if(tt[to]>n+1){ puts("-1"); exit(0); } if(vis[to]==0){ vis[to]=1; q.push(to); } } } vis[u]=0; } return 0; } ll st[E]; int main(){ ll T=1,S; while(T--){ n=read();m=read();S=read(); tot=0; memset(fir,0,sizeof(fir)); for(ll i=1;i<=m;i++){ ll x=read(),y=read();double z; cin>>z; add(x,y,(double)z); } for(ll i=0;i<=n;i++) dis[i]=2e18; dis[S]=0; memset(vis,0,sizeof(vis)); spfa(2); for(ll i=0;i<=n;i++) dis[i]=2e18; dis[S]=0; memset(vis,0,sizeof(vis)); spfa(S); for(ll i=1;i<=n;i++){ if(i==S) puts("0"); else if(dis[i]>=2e18) puts("NoPath"); else{ printf("%.0lf\n",dis[i]); } } } return 0; } |
