图论最短路 spfa-白红宇

图论最短路 spfa

阅读量：4493 次

发布时间：2019-06-08

本文共 1314 字，大约阅读时间需要 4 分钟。

链式前向星存图，遍历所有边，更新最短距离(队列实现，可判断负环

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;const int INF=0x3f3f3f3f;typedef pair
              
                pr;typedef long long ll;#define fi first#define se second#define me(x) memset(x, -1, sizeof(x))#define mem(x) memset(x, 0, sizeof(x))#define N 20000+5#define NIL -1struct node{ int next, to, w;}edge[N];int head[N], dist[N], vis[N], c[N];int n, m, cnt, flag;void init(){ cnt=0; flag=0; me(head); mem(vis); mem(c); for(int i=1; i<=n; i++) dist[i]=INF;}void add(int u, int v, int w){ edge[cnt].w=w; edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt++;}int spfa(int v){ queue
               
                 q; vis[v]=1; q.push(v); dist[v]=0; //c[v]=1; while(q.size()) { v=q.front(); q.pop(); vis[v]=0; for(int i=head[v]; ~i; i=edge[i].next) { int t=edge[i].to; if(dist[t]>dist[v]+edge[i].w) { dist[t]=dist[v]+edge[i].w; if(!vis[t]) //vis 必须在里面判断 dist的更新与此处无关 { vis[t]=1; q.push(t); c[t]++; if(c[t]>n) return 0; } } } } return 1;}int main(){ int i, j, k; int u, v, w; int x, y; while(cin>>n>>m) { if(!n && !m) break; init(); for(i=0; i
                
                 >u>>v>>w, add(u, v, w), add(v, u, w); x=1; k=1; k=spfa(x); if(k) cout<
                 
                  <