hdu1874畅通工程续-白红宇

hdu1874畅通工程续

阅读量：6306 次

发布时间：2019-06-22

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

floyd: 62MS

View Code

1 #include
      
        2 using namespace std ; 3 #define maxn 210 4 const int oo = 1<<28 ; 5 int map[maxn][maxn] ; 6 int n ; 7 void init() 8 { 9     for(int i=0; i
       
        map[i][k]+ map[k][j])23     map[i][j] = map[i][k] + map[k][j] ;24 }25 int main()26 {27     int m, a, b, c, s, t ;28     while(cin>>n>>m)29     {30         init() ;31         while(m--)32         {33             cin>>a>>b>>c ;34             if(map[a][b]>c)35             map[a][b] = map[b][a] = c ;36         }37         cin>>s>>t ;38         floyd() ;39         if(map[s][t]

dijkstra: 15MS

View Code

1 #include
      
        2 #include
        3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 9 #define MAX 0x3f3f3f3f10 #define N 21011 int num, road, dis[N], len[N][N];12 bool visit[N];13 14 15 void Dijkstra(int start)16 {17 int k, temp;18 memset(visit, 0, sizeof(visit));19 for(int i = 0; i < num; ++i) //初始化20 dis[i] = (i==start ? 0 : MAX);21 for(int i = 0; i < num; ++i)22 {23 temp = MAX;24 for(int j = 0; j < num; ++j) //查找最短路25 if(!visit[j] && dis[j] < temp)26 temp = dis[k = j];27 visit[k] = 1;28 for(int j = 0; j < num; ++j) //更新源点到其他点的最短路29 if(!visit[j] && dis[j] > dis[k] + len[k][j])30 dis[j] = dis[k] + len[k][j];31 }32 }33 34 int main()35 {36 int a, b, cost, start, end;37 while(scanf("%d%d", &num, &road) != EOF)38 {39 memset(len, MAX, sizeof(len));40 for(int i = 0; i < road; ++i)41 {42 scanf("%d%d%d", &a, &b, &cost);43 if(cost < len[a][b]) //一条路可以有多个cost，记录最小的。注意~~~44 len[a][b] = len[b][a] = cost;45 }46 scanf("%d%d", &start, &end);47 Dijkstra(start);48 if(dis[end] == MAX) printf("-1\n");49 else printf("%d\n", dis[end]);50 }51 return 0;52 }