Hoj 2047 106 miles to Chicago

Dijkstra. 只不過是把原先的普遍的最短單源路徑當作最大單源路徑來求。且運算符是乘法而不是加法。用Double來存儲，細節部分需要雕琢一下再提交。 題目：  #include <iostream>   #include <stdio.h>   #include <string.h>   #include <queue>   #include <math.h>   #include <algorithm>      using namespace std;      double map[102][102];   double dist[102];   int visited[102];      int main()   {      #ifndef ONLINE_JUDGE       freopen("in.txt","r",stdin);   #endif       int n,m;       while(scanf(" %d %d",&n,&m) == 2)       {           memset(map,0,sizeof(map));           for(int i=0; i<m; i++)           {               int a,b;               double p;               scanf(" %d %d %lf",&a,&b,&p);               map[a-1][b-1] = map[b-1][a-1] = p;           }           for(int i=0; i<n; i++)           {               map[i][i] = 100;           }              memset(dist,0,sizeof(dist));           memset(visited,0,sizeof(visited));              dist[0] = 100;           for(int i=0; i<n; i++)           {               double max = 0;               int k = 0;               for(int j=0; j<n; j++)               {                   if(visited[j] == 0 && dist[j]>max)                   {                       max = dist[j];                       k = j;                   }               }               visited[k] = 1;               for(int j=0; j<n; j++)               {                   if(dist[j] < dist[k] * map[k][j]/100)                   {                       dist[j] = dist[k] * map[k][j]/100;                   }               }           }           printf("%.6lf percent\n",dist[n-1]);       }       return 0;   }