acm1217教训

能用容器去做的用容器做，尽量少用数组，即使自己明确其数量的上届；

#include<iostream>

#include<cstring>

#include<map>//后来我用了一个map容器才能通过，如果自己建立数组就是不过，不知道到底哪里超出了；它明明说的是少于30个，现在做题题意也欺骗人了；

using namespace std;

const int N=;

int ok;

map<string,int>my_map;

void nameinput(int n)

{

    string name;

    for(int i=;i<=n;i++)

    {

        cin>>name;

        my_map[name]=i;

    }

}

double money[N][N];

void Link(int n,int m)

{

    //memset(money,-1,sizeof(money));

    for(int i=;i<=n;i++)

    for(int j=;j<=n;j++)

    money[i][j]=(i==j)?:;

    string name1,name2;

    double rate;

    for(int i=;i<=m;i++)

    {

        cin>>name1>>rate>>name2;

        money[my_map[name1]][my_map[name2]]=rate;

    }

    my_map.clear();

}

void deal(int n)

{

    for(int k=;k<=n;k++)

for(int i=;i<=n;i++)

for(int j=;j<=n;j++)

{

if(money[i][j]<money[i][k]*money[k][j])

money[i][j]=money[i][k]*money[k][j];

}

for(int i=;i<=n;i++)

if(money[i][i]>)//求回路中两点距离；

{

    ok=;break;

}

}

int main()

{

    int n,m;

        int count=;

    while(cin>>n&&n)

    {

        nameinput(n);

        cin>>m;

        ok=;

        Link(n,m);

        deal(n);

        if(ok==)cout<<"Case "<<count<<": Yes\n";

        else cout<<"Case "<<count<<": No\n";

        count++;

    }

    return ;

}
 

下面是超时代码：

 #include<iostream>

 #include<cstring>

 #include<map>

 using namespace std;

 const int N=;

 int ok;

 int vis[N];

 map<string,int>my_map;

 string Name[N];

 void nameinput(int n)

 {

     string name;

     for(int i=;i<=n;i++)

     {

         cin>>name;

         my_map[name]=i;

     }

 }

 double money[N][N];

 void Link(int n,int m)

 {

     for(int i=;i<=n;i++)

     for(int j=;j<=n;j++)

     money[i][j]=(i==j)?:;

     string name1,name2;

     double rate;

     for(int i=;i<=m;i++)

     {

         cin>>name1>>rate>>name2;

         money[my_map[name1]][my_map[name2]]=rate;

     }

     my_map.clear();

 }

 void process(int n,int start,int sub,double result)

 {

     if(sub==start)

     {

         if(result>)ok=;

         return;

     }

     double re=result;

     if(ok==)

     for(int i=;i<=n;i++)

     {

         if(money[sub][i]!=-&&!vis[i])

         {

             vis[i]=;

             re=result*money[sub][i];

             process(n,start,i,re);

             vis[i]=;

         }

         if(ok==)return;

     }

 }

 int main()

 {

     int n,m;

         int count=;

     while(cin>>n&&n)

     {

         memset(vis,,sizeof(vis));

         nameinput(n);

         cin>>m;

         ok=;

         Link(n,m);

         for(int i=;i<=n;i++)

         {

             for(int j=;j<=n;j++)

             if(money[i][j]!=-)

             {

                 vis[j]=;

                 process(n,i,j,1.0*money[i][j]);

                 vis[j]=;

             }

         }

         if(ok==)cout<<"Case "<<count<<": Yes\n";

         else cout<<"Case "<<count<<": No\n";

         count++;

     }

     return ;

 }