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 } /* 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]; } } } */