思路

先以所有顶点距离0等价超源检测全图负环，不能只查S可达部分；无负环再算S单源最短路，严格区分-1与NoPath，重边和自环按题面未排除而正确处理；n1000/m10万，带提前终止的Bellman-Ford。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
struct E{int u,v,w;};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,m,s;cin>>n>>m>>s;--s;vector<E>e(m);for(auto &a:e){cin>>a.u>>a.v>>a.w;--a.u;--a.v;}vector<long long>global(n,0);for(int i=0;i<n;i++){bool changed=false;for(auto a:e)if(global[a.v]>global[a.u]+a.w){global[a.v]=global[a.u]+a.w;changed=true;}if(!changed)break;if(i==n-1){cout<<-1<<'\n';return 0;}}const long long INF=(1LL<<60);vector<long long>d(n,INF);d[s]=0;for(int i=1;i<n;i++){bool changed=false;for(auto a:e)if(d[a.u]!=INF&&d[a.v]>d[a.u]+a.w){d[a.v]=d[a.u]+a.w;changed=true;}if(!changed)break;}for(long long value:d)if(value==INF)cout<<"NoPath\n";else cout<<value<<'\n';}