最短路(Floyd_Warshall) POJ 2240 Arbitrage

题目传送门

 /*
最短路:Floyd模板题
只要把+改为*就ok了,热闹后判断d[i][i]是否大于1
文件输入的ONLINE_JUDGE少写了个_,WA了N遍:)
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
using namespace std; const int MAXN = 1e6 + ;
const int INF = 0x3f3f3f3f;
double d[][]; void Floyd_Warshall(int n)
{
for (int k=; k<=n; ++k)
{
for (int i=; i<=n; ++i)
{
for (int j=; j<=n; ++j)
{
if (d[i][j] < d[i][k] * d[k][j])
{
d[i][j] = d[i][k] * d[k][j];
}
}
}
} for (int i=; i<=n; ++i)
{
if (d[i][i] > )
{
puts ("Yes"); return ;
}
} puts ("No"); return ;
} int main(void) //POJ 2240 Arbitrage
{
#ifndef ONLINE_JUDGE
freopen ("F.in", "r", stdin);
#endif int n, num; int cas = ;
while (cin >> n && n)
{
for (int i=; i<=n; ++i)
{
for (int j=; j<=n; ++j)
{
if (i == j) d[i][j] = ;
else d[i][j] = ;
}
} map<string, int> m;
string s, s1, s2;
for (int i=; i<=n; ++i)
{
cin >> s;
m[s] = i;
} cin >> num;
for (int i=; i<=num; ++i)
{
double w;
cin >> s1 >> w >> s2;
d[m[s1]][m[s2]] = w;
} cout << "Case " << ++cas << ": ";
Floyd_Warshall (n);
} return ;
}
上一篇:让 ASP.NET JS验证和服务端的 双验证 更简单


下一篇:点餐系统web版功能需求