#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define INF 0x7fffffffstruct edge{    int t;    long long d;};vector
         
           g[20005];int n, m, p, q;void Spfa(int x){ int minn = 0; queue
          
           q; long long dis[20005]; bool vis[20005]; memset(vis,false,sizeof(vis)); for(int i = 0; i <= n; i++) dis[i] = INF; vis[x] = true; dis[x] = 0; q.push(x); while(q.size()) { int tmp = q.front(); q.pop(); vis[tmp] = false; for(int i = 0; i < g[tmp].size(); ++i) { if(dis[g[tmp][i].t] > dis[tmp] + g[tmp][i].d) { dis[g[tmp][i].t] = dis[tmp] + g[tmp][i].d; if(vis[g[tmp][i].t] == false) { q.push(g[tmp][i].t); vis[g[tmp][i].t] = true; } } } } for(int i = 2; i <= n; ++i) { cout<
           
            <
            
             >n>>m; q = 1; for(int i = 0; i < m; ++i) { int x, y, s; edge e; cin>>x>>y>>s; e.t = y; e.d = s; g[x].push_back(e); } Spfa(q); return 0;}
            
           
          
         
        
       
      
     
    

算法训练 最短路

版权声明：本文为博主原创文章，未经博主允许不得转载。