HDU 1596 find the safest road (最短路)

find the safest road

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6973 Accepted Submission(s): 2469


Problem Description XX星球有很多城市，每個城市之間有一條或多條飛行通道，但是並不是所有的路都是很安全的，每一條路有一個安全系數s,s是在 0 和 1 間的實數(包括0，1)，一條從u 到 v 的通道P 的安全度為Safe(P) = s(e1)*s(e2)…*s(ek) e1,e2,ek是P 上的邊 ，現在8600 想出去旅游，面對這這麼多的路，他想找一條最安全的路。但是8600 的數學不好，想請你幫忙 ^_^
Input 輸入包括多個測試實例，每個實例包括：
第一行：n。n表示城市的個數n<=1000;
接著是一個n*n的矩陣表示兩個城市之間的安全系數，(0可以理解為那兩個城市之間沒有直接的通道)
接著是Q個8600要旅游的路線,每行有兩個數字，表示8600所在的城市和要去的城市
Output 如果86無法達到他的目的地，輸出"What a pity!",
其他的輸出這兩個城市之間的最安全道路的安全系數,保留三位小數。
Sample Input

3
1 0.5 0.5
0.5 1 0.4
0.5 0.4 1
3
1 2
2 3
1 3

Sample Output

0.500
0.400
0.500

Author ailyanlu
Source HDU 2007-Spring Programming Contest - Warm Up （1）
Recommend 8600 | We have carefully selected several similar problems for you: 1217 1598 1142 1690 1385

題意很明白了，還是一些小細節的問題，模板打多了毀帶來一些思維僵化，
所以找一些模板題但又有些變通的題最好了。

代碼：1671MS

#include 
#include 
#include 
#include 
using namespace std;
#define M 1050
int n,m;
double map[M][M],dis[M];
void Dijkstra(int x,int y)
{

  bool v[M]={0};
  int i,j;
  for(i=1;i<=n;i++) dis[i]=(i==x?1:0);
  for(i=1;i<=n;i++)
  {
      int k;
      double Min=0;  //在這裡WA了一發，模板打多了就只會int了。
      for(j=1;j<=n;j++) if(!v[j] && dis[j]>Min) Min=dis[k=j];
      v[k]=1;
      for(j=1;j<=n;j++) dis[j]=max(dis[j],dis[k]*map[k][j]);
  }
  if(dis[y]) printf("%.3lf\n",dis[y]);
  else printf("What a pity!\n");
}

int main()
{
  int i,j;
  int a,b,c;
  while(scanf("%d",&n)!=EOF && n)
  {
      memset(map,0,sizeof(map));
      for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
      {
          scanf("%lf",&map[i][j]);
      }
      //題目給的是鄰接矩陣，所以不要初始化了。
      scanf("%d",&m);
      for(i=1;i<=m;i++)
      {
       scanf("%d%d",&a,&b);
       Dijkstra(a,b);
      }
  }
  return 0;
}

我個人認為用Floyd算法應該也可以，就是時限的問題了。
這題應該要用SPFA算法去做，不過時限放的很寬，所以就變成模板題了。
其實精品題和模板題差距就在時限和思想兩方面。