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