貌似可以最短路时同时判定负环啊。

但我不想这样做。

于是写了一个dfs版的判环，bfs版的求最短路。

代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define N 1005#define M 1000005#define inf 0x3f3f3f3fusing namespace std;inline int read(){    int ans=0,w=1;    char ch=getchar();    while(!isdigit(ch)){
   if(ch=='-')w=-1;ch=getchar();}    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();    return ans*w;}int n,m,first[N],cnt=0,d[N];bool in[N];struct edge{
   int v,next,w;}e[M<<1];inline void add(int u,int v,int w){e[++cnt].v=v,e[cnt].w=w,e[cnt].next=first[u],first[u]=cnt;}inline bool spfa(int p){    in[p]=true;    for(int i=first[p];i;i=e[i].next){        int v=e[i].v;        if(d[v]>d[p]+e[i].w){            d[v]=d[p]+e[i].w;            if(in[v]||spfa(v))return in[p]=false,true;        }    }    return in[p]=false;}inline bool check(){    for(int i=1;i<=n;++i)if(spfa(i))return true;    return false;}inline void Spfa(int s){    queue
         
          q; for(int i=1;i<=n;++i)d[i]=inf,in[i]=false; q.push(s),d[s]=0,in[s]=true; while(!q.empty()){ int x=q.front(); q.pop(); in[x]=false; for(int i=first[x];i;i=e[i].next){ int v=e[i].v; if(d[v]>d[x]+e[i].w){ d[v]=d[x]+e[i].w; if(!in[v])in[v]=true,q.push(v); } } }}int main(){ int s; n=read(),m=read(),s=read(); for(int i=1;i<=m;++i){ int u=read(),v=read(),w=read(); add(u,v,w); } if(check()){ printf("-1");return 0;} Spfa(s); for(int i=1;i<=n;++i){ if(d[i]==inf)puts("NoPath"); else printf("%d\n",d[i]); } return 0;}