poj 2472

[cpp]
//易做图这种水题WA的泪流满面
//floyd的中转点要放在最上层循环比较好

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define MAXN 110

int n,m;

double dist[MAXN][MAXN];

int a,b,p;

void Floyd()
{
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
    {
      for(int j = 1; j <= n; j++)
    {
          if(dist[i][j] < dist[i][k]*dist[k][j])
        dist[i][j] = dist[i][k]*dist[k][j];
    }
    }
}

int main()
{
while(scanf("%d",&n)!=EOF &&n)
    {
      if(n == 0)
    break;
      cin>>m;
      for(int i = 1; i <= n; i++)
    {
      for(int j = 1; j <= n; j++)
        {
          if(i == j)
        dist[i][j] = 1;
          else
        dist[i][j] = 0;
        }
    }
      // while(m--)
      for(int i = 0; i < m; i++)
    {
      cin>>a>>b>>p;
      dist[a][b] = dist[b][a] =(double)p/100;

    }
      Floyd();
      printf("%.6lf percent\n",dist[1][n]*100);

    }

return 0;

}

//易做图这种水题WA的泪流满面
//floyd的中转点要放在最上层循环比较好

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define MAXN 110

int n,m;

double dist[MAXN][MAXN];

int a,b,p;

void Floyd()
{
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
    {
      for(int j = 1; j <= n; j++)
{
       if(dist[i][j] < dist[i][k]*dist[k][j])
  dist[i][j] = dist[i][k]*dist[k][j];
}
    }
}

int main()
{
while(scanf("%d",&n)!=EOF &&n)
    {
      if(n == 0)
break;
      cin>>m;
      for(int i = 1; i <= n; i++)
{
   for(int j = 1; j <= n; j++)
     {
       if(i == j)
  dist[i][j] = 1;
       else
  dist[i][j] = 0;
     }
}
      // while(m--)
      for(int i = 0; i < m; i++)
{
   cin>>a>>b>>p;
   dist[a][b] = dist[b][a] =(double)p/100;

}
      Floyd();
      printf("%.6lf percent\n",dist[1][n]*100);

    }

return 0;

}

补充：软件开发 , C++ ,