HD1874 畅通工程续

思考：最短路入门题目，可以用求最短路的算法，数据量也不大，比如Dijkstra, floy 或者SPFA算法。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; const int maxn = 210; const int maxm = 1100; const int INF = 0x7fffffff; int gn, gm; bool inque[maxn]; int dist[maxn]; queue
        
          Q; vector
         
           > g[maxn + 10]; void spfa(const int s, const int t) { int i; memset(inque, false, sizeof(inque)); for(i = 0; i < gn; i++) dist[i] = INF; dist[s] = 0; while(!Q.empty()) Q.pop();//清空队列. Q.push(s); inque[s] = true; while(!Q.empty()) { int u = Q.front(); Q.pop(); for(i = 0; i < (int)g[u].size(); i++) { int t = g[u][i].first; if(dist[u] != INF && g[u][i].second != INF && dist[u]+g[u][i].second < dist[t]) { dist[t] = dist[u] + g[u][i].second; if(!inque[t]) { inque[t] = true; Q.push(t); } } } inque[u] = false; } if(dist[t] != INF) { printf("%d\n", dist[t]); } else printf("-1\n"); } void init() { int i; for(i = 0; i < maxn; i++) { g[i].clear(); } } int main() { int i; int x, y, w; pair
          
            t; while(scanf("%d%d", &gn, &gm) != EOF) { init();//清空容器. for(i = 0; i < gm; i++) { scanf("%d%d%d", &x, &y, &w); t.first = y; t.second = w; g[x].push_back(t); t.first = x; g[y].push_back(t); } int s, tt; scanf("%d%d", &s, &tt); spfa(s, tt); } return 0; }