hdu(1596)

旧城等待， 2021-12-22 09:45 167阅读 0赞

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] 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 \}

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] 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\];  
\}  
\}  
\} \*/

转载于:https://www.cnblogs.com/FCWORLD/archive/2011/03/22/1991616.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/3a98b72ee22e4158a712a0365a9c7aff.png