| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
贴一个 797ms 的代码好了……居然能跑那么慢#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#include <string>
using namespace std;
map<string,int> mymap;
double mat[100][100];
int main()
{
int n, tot = 0;
while(cin>>n,n)
{
mymap.clear();
memset(mat,0,sizeof(mat));
string s1,s2;
for(int i=0;i<n;i++)
{
cin>>s1;
mymap[s1] = i;
}
int m;
double x;
cin>>m;
for(int i=0;i<m;i++)
{
cin>>s1>>x>>s2;
int t1 = mymap[s1];
int t2 = mymap[s2];
if(!mat[t1][t2])
mat[t1][t2] = x;
else
if(mat[t1][t2]<x)
mat[t1][t2] = x;
}
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
if(mat[i][k])
for(int j=0;j<n;j++)
if(mat[k][j])
if(!mat[i][j])
mat[i][j] = mat[i][k]*mat[k][j];
else
mat[i][j] = max(mat[i][j],mat[i][k]*mat[k][j]);
bool ans = false;
for(int i=0;i<n;i++)
if(mat[i][i]>1)
{
ans = true;
break;
}
if(ans) cout<<"Case "<<++tot<<": Yes\n";
else cout<<"Case "<<++tot<<": No\n";
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator