Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴一个 797ms 的代码好了……居然能跑那么慢

Posted by yyii1111 at 2012-02-13 16:25:04 on Problem 2240
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator