Einbahnstrasse HDU2923

基础2923题

处理输入很麻烦

有可能一个城市有多辆破车要拖   应该严谨一点的 考虑所有情况

#include<bits/stdc++.h>

using namespace std;

int m1[][];

int vis[];int dis[];

#define INF 99999

int n,e,cas;

int a1[];int a2[];

void dijkstra(int v0)

{

    memset(vis,,sizeof(vis));

    for(int i=;i<=n;i++)dis[i]=m1[v0][i];

   //  for(int i=1;i<=n;i++)printf("%d ",dis[i]);cout<<endl;

    vis[v0]=;

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

    {

        int minn=INF,u=v0;

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

        {

            if(vis[j]==&&dis[j]<minn)

            {

                u=j;minn=dis[j];

            }

        }

        vis[u]=;

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

        {

            if(vis[j]==&&dis[u]+m1[u][j]<dis[j])

            {

                dis[j]=dis[u]+m1[u][j];

            }

        }

    }

}

int a[];

int main()

{

   int c1,cas;map<string,int>ma;

   int cas1=;

   while(scanf("%d%d%d",&n,&c1,&cas)==&&(n+c1+cas))

   {   ma.clear();

      memset(a,,sizeof(a));

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

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

       {

           if(i==j)m1[i][j]=;

           else m1[i][j]=INF;

       }

       int c=;string s;cin>>s;

       ma[s]=n;

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

       {

           cin>>s;

           if(!ma[s])ma[s]=++c;

           a[i]=ma[s];

       }

      // printf("pl10\n");

       string s1,s2,s3;

       while(cas--)

       {

           cin>>s1>>s2>>s3;

           int val=;

           //cout<<s1<<endl;

          // cout<<s2<<endl;

         //  cout<<s3<<endl;

           val=s2[]-'';

           int i=;

           while(isdigit(s2[i])){ val=val*+s2[i]-'';   i++;}

       //    printf("val=%d\n",val);

           if(!ma[s1])ma[s1]=++c;

           if(!ma[s3])ma[s3]=++c;

           if(s2[]=='<'&&m1[ ma[s3] ][ ma[s1] ]>val)m1[ ma[s3] ][ ma[s1] ]=val;

           if(s2[ s2.size()- ]=='>'&&m1[ ma[s1] ][ ma[s3] ]>val)m1[ ma[s1] ][ ma[s3] ]=val;

       }

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

      // {

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

      //      printf("%d ",m1[i][j]);

      //     cout<<endl;

     //  }

       int sum=;

      // for(int i=1;i<=c1;i++)printf("%d ",a[i]);cout<<endl;

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

       {

           dijkstra( a[i] );sum+=dis[n];

       }

       //printf("%d\n",sum);

       dijkstra(n);

       for(int i=;i<=c1;i++)sum+=dis[ a[i] ];

       printf("%d. %d\n",++cas1,sum);

   }

}