POJ 1135 -- Domino Effect（单源最短路径）

POJ 1135 -- Domino Effect（单源最短路径）

题目描述：
你知道多米诺骨牌除了用来玩多米诺骨牌游戏外，还有其他用途吗？多米诺骨牌游戏：取一些多米诺骨牌，竖着排成连续的一行，两张骨牌之间只有很短的空隙。如果排列得很好，当你推倒第 1张骨牌，会使其他骨牌连续地倒下（这就是短语“多米诺效应”的由来）。然而当骨牌数量很少时，这种玩法就没多大意思了，所以一些人在 80 年代早期开创了另一个极端的多米诺骨牌游戏：用上百万张不同颜色、不同材料的骨牌拼成一幅复杂的图案。他们开创了一种流行的艺术。在这种骨牌游戏中，通常有多行骨牌同时倒下。你的任务是编写程序，给定这样的多米诺骨牌游戏，计算后倒下的是哪一张骨牌、在什么时间倒下。这些多米诺骨牌游戏包含一些“关键牌”，他们之间由一行普通骨牌连接。当一张关键牌倒下时，连接这张关键牌的所有行都开始倒下。当倒下的行到达其他还没倒下的关键骨牌时，则这些关键骨牌也开始倒下，同样也使得连接到它的所有行开始倒下。每一行骨牌可以从两个端点中的任何一张关键牌开始倒下，甚至两个端点的关键牌都可以分别倒下，在这种情形下，该行后倒下的骨牌为中间的某张骨牌。假定骨牌倒下的速度一致。

输入描述：
输入文件包含多个测试数据，每个测试数据描述了一个多米诺骨牌游戏。每个测试数据的第 1行为两个整数：n和m，n表示关键牌的数目，1≤n<500；m表示这 n张牌之间用 m行普通骨牌连接。n 张关键牌的编号为 1～n。每两张关键牌之间至多有一行普通牌，并且多米诺骨牌图案是连通的，也就是说从一张骨牌可以通过一系列的行连接到其他每张骨牌。接下来有 m行，每行为 3个整数：a、b和t，表示第 a张关键牌和第 b张关键牌之间有一行普通牌连接，这一行从一端倒向另一端需要 t 秒。每个多米诺骨牌游戏都是从推倒第 1 张关键牌开始的。输入文件后一行为 n = m = 0，表示输入结束。

输出描述：
对输入文件中的每个测试数据，首先输出一行"System #k"，其中 k为测试数据的序号；然后再输出一行，首先是后一块骨牌倒下的时间，精确到小数点后一位有效数字，然后是后倒下骨牌的位置，这张后倒下的骨牌要么是关键牌，要么是两张关键牌之间的某张普通牌。输出格式如样例输出所示。如果存在多个解，则输出任意一个。每个测试数据的输出之后输出一个空行。

解题思路：

最后倒下的牌有两种情形

1.最后倒下的是关键牌，其时间及位置就是第1张关键牌到其他关键牌中最短路径的最大值及对应的关键牌

2.最后倒下的是两张关键牌之间的普通牌，其时间为两张关键牌倒下的时间的一半加上这一行倒下的时间的一半，位置为这两张牌中间的某张牌，不一定是正中间那张，但不用求出具体是哪一张牌。

  1 #include<iostream>
  2 #include<cstring>
  3 using namespace std;
  4 #define MAXN 500
  5 #define INF 1000000 
  6 int n,m;///n为关键牌的数量，m为关键牌之间的行数
  7 int Edge[MAXN][MAXN];//邻接矩阵 
  8 int time[MAXN];//第i张关键牌倒下的时间（最先推倒_(:зゝ∠)_第0张骨牌，存储时序号已减一）
  9 int S[MAXN];//表示第i张骨牌是否倒下
 10 int Count = 1;
 11 void solve_case(int v0)//v0为起始点 
 12 {///使用Dijkstra 
 13      //首先初始化,将v0加入到顶点集合S
 14      for(int i=0;i<n;i++){
 15          time[i] = Edge[v0][i];S[i] = 0;
 16      } 
 17      S[v0] = 1;time[v0] = 0;
 18      //计算最短路径
 19      for(int i=0;i<n-1;i++)//从顶点0确定n-1条最短路径
 20      {
 21          int min = INF,u=0;
 22          for(int j=0;j<n;j++)//从time[]找出最短的一条边
 23          {
 24              if(!S[j] && time[j]<min){
 25                  min = time[j];u = j;
 26              }
 27           } 
 28           S[u] = 1;///将u加入到S中
 29           for(int j=0;j<n;j++)///更新与u相连通的点
 30           {
 31               if(!S[j] && Edge[j][u]!=INF && time[u]+Edge[j][u]<time[j])
 32               {
 33                   time[j] = time[u]+Edge[j][u];
 34               }
 35            } 
 36       }
 37       
 38       //1.最后倒下的是关键牌，其时间及位置就是第1张关键牌到其他关键牌中最短路径的最大值及对应的关键牌 
 39      double time1 = -INF;int pos;
 40      for(int i=0;i<n;i++)
 41      {
 42          if(time[i]>time1) {
 43              time1 = time[i];pos = i;
 44          }
 45       } 
 46       //2.最后倒下的是两张关键牌之间的普通牌，其时间为两张关键牌倒下的时间的一半加上这一行倒下的时间的一半，
 47       double time2 = -INF,t;int pos1,pos2;
 48       for(int i=0;i<n;i++)
 49       {
 50           for(int j=0;j<n;j++)
 51           {
 52               t = (time[i]+time[j]+Edge[i][j])/2.0;
 53               if(Edge[i][j]<INF && t>time2){
 54                   time2 = t;pos1 = i;pos2 = j;
 55               }
 56           }
 57        } 
 58        cout<<"System #"<<Count++<<endl;
 59        cout<<"The last domino falls after ";
 60        if(time1>=time2){
 61            ///某关键牌最后倒下
 62            ///如果相等输出第一个 ，因为有只有一条边的情况 
 63            printf("%.1f ",time1); 
 64            cout<<"seconds, at key domino ";
 65            cout<<pos+1<<"."<<endl;
 66        }else{
 67                printf("%.1f ",time2);
 68             cout<<"seconds, between key dominoes ";
 69             cout<<pos1+1<<" and "<<pos2+1<<"."<<endl; 
 70        }
 71        
 72     
 73 }
 74 
 75 int read_case()//读入数据 
 76 {
 77     cin>>n>>m;
 78     if(n==0) return 0;
 79     for(int i=0;i<n;i++)
 80     {
 81         for(int j=0;j<n;j++) Edge[i][j] = INF;///初始化邻接矩阵 
 82      } 
 83     //memset(Edge,INF,sizeof(Edge));///初始化邻接矩阵 
 84     int v1,v2,t;
 85     for(int i=0;i<m;i++)
 86     {
 87         cin>>v1>>v2>>t;
 88         Edge[v1-1][v2-1] = Edge[v2-1][v1-1] = t;
 89     }
 90     return 1;
 91 }
 92 int main()
 93 {
 94     while(read_case())
 95     {
 96         solve_case(0);
 97         cout<<endl;
 98     }
 99     return 0;
100  }