http://vijos.org/p/1391

SPFA，感觉不是真正意义上的SPFA。。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define ms(i,j) memset(i, j, sizeof(i));using namespace std;const int maxn = 2000 + 5;int w[maxn][maxn];int edge[maxn][maxn];int dis[maxn];int ex[maxn];queue
         
           q;int n;int main () { scanf("%d", &n); int a,b,c; for (int i=1;i<=n;i++)for (int j=1;j<=n;j++) w[i][j]=100000000; while (scanf("%d%d%d", &a, &b, &c)==3&&(a||b||c)) { w[a][b]=c; } ms(dis,0);ms(ex,false); dis[1] = 100000000;ex[1]=true; q.push(1); while(!q.empty()) { int u = q.front();q.pop();ex[u]=false; for (int i=1;i<=n;i++) { if (w[u][i]!=100000000&&dis[i]