基础2923题
处理输入很麻烦
有可能一个城市有多辆破车要拖 应该严谨一点的 考虑所有情况
#include<bits/stdc++.h> using namespace std; int m1[1005][1005]; int vis[1005];int dis[1005]; #define INF 99999 int n,e,cas; int a1[1000];int a2[1000]; void dijkstra(int v0) { memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++)dis[i]=m1[v0][i]; // for(int i=1;i<=n;i++)printf("%d ",dis[i]);cout<<endl; vis[v0]=1; for(int i=0;i<n-1;i++) { int minn=INF,u=v0; for(int j=1;j<=n;j++) { if(vis[j]==0&&dis[j]<minn) { u=j;minn=dis[j]; } } vis[u]=1; for(int j=1;j<=n;j++) { if(vis[j]==0&&dis[u]+m1[u][j]<dis[j]) { dis[j]=dis[u]+m1[u][j]; } } } } int a[1000]; int main() { int c1,cas;map<string,int>ma; int cas1=0; while(scanf("%d%d%d",&n,&c1,&cas)==3&&(n+c1+cas)) { ma.clear(); memset(a,0,sizeof(a)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(i==j)m1[i][j]=0; else m1[i][j]=INF; } int c=0;string s;cin>>s; ma[s]=n; for(int i=1;i<=c1;i++) { cin>>s; if(!ma[s])ma[s]=++c; a[i]=ma[s]; } // printf("pl10 "); string s1,s2,s3; while(cas--) { cin>>s1>>s2>>s3; int val=0; //cout<<s1<<endl; // cout<<s2<<endl; // cout<<s3<<endl; val=s2[2]-'0'; int i=3; while(isdigit(s2[i])){ val=val*10+s2[i]-'0'; i++;} // printf("val=%d ",val); if(!ma[s1])ma[s1]=++c; if(!ma[s3])ma[s3]=++c; if(s2[0]=='<'&&m1[ ma[s3] ][ ma[s1] ]>val)m1[ ma[s3] ][ ma[s1] ]=val; if(s2[ s2.size()-1 ]=='>'&&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=0; // for(int i=1;i<=c1;i++)printf("%d ",a[i]);cout<<endl; for(int i=1;i<=c1;i++) { dijkstra( a[i] );sum+=dis[n]; } //printf("%d ",sum); dijkstra(n); for(int i=1;i<=c1;i++)sum+=dis[ a[i] ]; printf("%d. %d ",++cas1,sum); } }