10086. 「一本通 3.3 练习 3」Easy SSSP

(Updated: )
oi
,

题意

给你一个图，问从源点到每个节点的最短路径分别是多少。 如果存在负权回路，只输出一行 -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;
}