Loj10086 Easy SSSP

 先用DFS判断负环，然后跑最短路即可。

DFS具体判断负环的方法是：记录一个vis数组，表示在你这次搜索过程中有没有走到这个点，如果在搜索的时候，发现这个目标点vis==1了，并且你还可以更新这个目标点的dis，那么就存在负环。因为这就相当于你跑完一圈，dis又少了，那么这个环肯定是负的。

这里有一个优化：是大佬YSF、SYF和我们清华毕业的数学老师姚璐提出并证明的。一般判断负环时，我们会把dis初始值赋成INF，但是实际上，我们可以赋0。相当于DFS跑最短路的时候，遇到正边就不跑了，这样会节省很大的时间复杂度。那么怎么证明正确性呢？

首先，我们需要证明一点，对于一个负环，一定有一个点，从这个点到第起始点的所有边权都为负，因为如果有正的，dis为0的情况可能会被正的卡住。那么又怎么证明这个呢？

我们可以画一个函数图像，x坐标表示负环上的每个点，y表示到x点时经过的边权。画出来后，你会发现，一定有一个峰值，然后对于这个峰值建系，它右侧的值全都是负的了。

具体代码如下（注意我的dis赋成0也可以AC，也是一个上面说法的验证）：

#include 
#include 
#include 
#include 
#include 
#include 
#define REP(i,k,n) for(int i=k;i<=n;i++)
#define in(a) a=read()
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar())
        if(ch=='-')
            f=-1;
    for(;isdigit(ch);ch=getchar())
        x=x*10+ch-'0';
   return x*f;
}
int T;
int flag=0;
int n,m,s;
int total=0,nxt[200010],head[200050],to[600510],val[605010];
int vis[200050],dis[100550],book[200050];
int q[1000010];
inline void adl(int a,int b,int c){
    total++;
    to[total]=b;
    val[total]=c;
    nxt[total]=head[a];
    head[a]=total;
    return ;
}
queue <int> Q;
inline void dfs(int u){
    book[u]=1;
    for(int e=head[u];e;e=nxt[e]){
        if(dis[to[e]]>dis[u]+val[e]){
            dis[to[e]]=dis[u]+val[e];
            if(vis[to[e]]){
                flag=1;
                return ;
            }
            if(flag)
                return ;
            vis[to[e]]=1;
            dfs(to[e]);
            vis[to[e]]=0;
        }
    }
    return ;
}
void SPFA(int st){
    memset(vis,0,sizeof(vis));
    memset(dis,127,sizeof(dis));
    int hea=1,tail=1;
    //q[hea]=st;
    Q.push(st);
    dis[st]=0;
    while(!Q.empty()/*tail>=hea*/){
        int u=Q.front();
        //hea++;
        Q.pop();
        vis[u]=0;
        for(int e=head[u];e;e=nxt[e])
            if(dis[to[e]]>dis[u]+val[e]){
                dis[to[e]]=dis[u]+val[e];
                if(!vis[to[e]]){
                    vis[to[e]]=1;
                    Q.push(to[e]);
                }
            }
    }
    return ;
}
int main()
{
    total=flag=0;
    //memset(dis,127,sizeof(dis));
    in(n);in(m);in(s);
    int a,b,c;
    REP(i,1,m){
        in(a);in(b);in(c);
        adl(a,b,c);
    }
    REP(i,1,n)
        if(!book[i]){
            memset(vis,0,sizeof(vis));
                 dfs(i);
                 if(flag)  break;
             }
    if(flag){
        cout<<-1<<endl;
        return 0;
    }
    SPFA(s);
        REP(i,1,n)
            if(dis[i]>999999999)
                cout<<"NoPath"<<endl;
            else  cout<endl;
}