POJ-1135 Domino Effect---最短路Dijk

题目链接：

题目大意：

有N个关键的多米诺骨牌，这些牌通过一些路径相连接，这些路径是由一排其他骨牌构成的。已知每一条路径上的骨牌倒下需要的时间。现在从把编号为1的关键骨牌推倒，问多长时间后所有的骨牌（包括关键牌和它们之间的路径上的骨牌）都倒下，时间精确到小数点后一位。

思路：

先用dijkstra算法计算每一张骨牌倒下的时间d[i],然后取最大值time1。

再每两张骨牌之间全部倒下的时间的最大值time2 = max{(d[i] + d[j] + Map[i][j]) / 2}

如果time1>=time2，那就是在某张关键牌处结束，不然则在两张关键牌中结束

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<stack>

 #include<map>

 #include<sstream>

 using namespace std;

 typedef long long ll;

 const int maxn =  + ;

 const int INF =  << ;

 int T, n, m, cases;

 int Map[maxn][maxn];

 bool v[maxn];

 int d[maxn];

 void dijkstra(int u0)

 {

     memset(v, , sizeof(v));

     for(int i = ; i <= n; i++)d[i] = (i == u0 ?  : INF);

     for(int i = ; i <= n; i++)

     {

         int x, m = INF;

         for(int j = ; j <= n; j++)if(!v[j] && d[j] <= m)m = d[x = j];

         v[x] = ;

         for(int j = ; j <= n; j++)

             d[j] = min(d[j], d[x] + Map[x][j]);//松弛操作

     }

 }

 int main()

 {

     while(cin >> n >> m)

     {

         if(!n && !m)break;

         for(int i = ; i <= n; i++)for(int j = ; j <= n; j++)Map[i][j] = INF;

         int x, y, z;

         for(int i = ; i < m; i++)

         {

             cin >> x >> y >> z;

             Map[x][y] = Map[y][x] = z;

         }

         dijkstra();

         double mintime1 = -INF, mintime2 = -INF;

         int ans, ans1, ans2;

         for(int i = ; i <= n; i++)

         {

             if(mintime1 < d[i])

             {

                 mintime1 = d[i];

                 ans = i;

             }

         }

         for(int i = ; i <= n; i++)

         {

             for(int j = ; j <= n; j++)

             {

                 if(Map[i][j] == INF)continue;

                 if(mintime2 < 1.0 * (d[i] + d[j] + Map[i][j]) / 2.0)

                 {

                    mintime2 = 1.0 * (d[i] + d[j] + Map[i][j]) / 2.0;

                    ans1 = i, ans2 = j;

                 }

             }

         }

         printf("System #%d\n", ++cases);

         if(mintime1 >= mintime2)printf("The last domino falls after %.1f seconds, at key domino %d.\n\n", mintime1, ans);

         else printf("The last domino falls after %.1f seconds, between key dominoes %d and %d.\n\n", mintime2, ans1, ans2);

     }

 }