hdu(1596)

dijkstra

 1 #include"iostream"
 2 using namespace std;
 3 double map[1010][1010];
 4 int visit[1010];
 5 double used[1010];
 6 int k;
 7 double _max=0;
 8 int i,j;
 9 int n,m,a,b;
10 int main()
11 {
12     
13     while(scanf("%d",&n)!=EOF)
14     {
15         memset(map,0,sizeof(map));
16         for(i=1;i<=n;i++)
17             for(j=1;j<=n;j++)
18                 scanf("%lf", &map[i][j]);
19             
20           scanf("%d",&m);
21             for(i=0;i<m;i++)
22            {
23                
24                scanf("%d%d",&a,&b);
25              
26       for(int p=1; p<=n; p++)
27       {
28          visit[p]=0;
29          used[p]=0;
30       }
31       used[a]=1;
32     
33         for(int q=1; q<=n; q++ )
34         {
35             _max=0;
36                     for(int s = 1; s<=n; s++)
37                      {
38                         if(!visit[s] && used[s]>_max)
39                         {
40                            _max = used[s];
41                            k=s;
42                          }
43                     }
44                       visit[k]=1;
45                       for(int p=1;p<=n;p++)
46                     {
47                         if(map[k][p]>0 && used[k]*map[k][p]>used[p])
48                               used[p]=used[k]*map[k][p];
49                     }
50                 }
51               if(used[b]==0)  printf("What a pity!\n");
52                      else printf("%.3lf\n",used[b]);
53             }
54      }
55     return 0;
56 }

folyd

/* for(k=1;k<=n;k++)
           {
               for(i=1;i<=n;i++)
               {
                   for(j=1;j<=n;j++)
                       if(map[i][k]*map[k][j]>map[i][j]) 
                        {
                            map[i][j]=map[i][k]*map[k][j];
                            map[j][i]=map[i][k]*map[k][j];
                       }
               }
           }*/