输出的时候犯了一个小错误："Yes"当作“YES”了。

这个题是很基础的最短路径题，不限次数倒买倒卖，求能否过一定的收益率（这里为1）。我记得uva上有一个题是问在t次交换内能否达到一定的汇率......那样似乎还要记录路径了......上次学校里搞选拔赛的时候做过，做不出。现在还是做不出 TAT

另，memset(a, 0, sizeof(a))对double数组无效。但可以写memset(a, 0x00, sizeof(a))

#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
#include <map>
using namespace std;

double a[30][30];
map<string, int> sm, dm;
int n, c = 0, ac;

int main()
{
 //ifstream cin("in.txt");
 while(cin >> n && n)
 {
  sm = dm;  
  int i, k, t, j;
  for(i = 0; i < n; i ++)
  {
   string s;
   cin >> s;
   sm[s] = i;
   for(k = 0; k < n; k ++)
   {
    a[i][k] = 0;  //清零
   }
  }
  cin >> t;
  for(i = 0; i < t; i ++)
  {
   string s0, s1; double td;
   cin >> s0 >> td >> s1;
   a[sm[s0]][sm[s1]] = td;
  }
  //pt();
  for(j = 0; j < n; j ++)
  {
   for(i = 0; i < n; i ++)
   {
    for(k = 0; k < n; k ++)
    {
     if(a[i][j] * a[j][k] > a[i][k])
      a[i][k] = a[i][j] * a[j][k];    //Floyd
    }
   }
  }
  //pt();
  ac = 0;
  for(i = 0; i < n; i ++)
  {
   if(a[i][i] > 1)
   {
    ac = 1;
    break;
   }
  }
  printf("Case %d: ", ++ c);
  if(ac)
   printf("Yes\n");
  else
   printf("No\n");
 }
 return 0;
}

评论