本文主要是介绍HDU 2112——HDU Today，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最小路径的题目，地名的处理是把各个地名标记序号即可。
需要注意的是这题是的公交起点站可到终点站，终点站也可到起点站。另外给出两个相同地点时，输出是0.
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF 1000000
int map[160][160],dis[160];
bool que[160];
char place[160][35];
int main()
{int i,j,sum,s,e,flag,cost;int n,min,k;char ch[35];while(scanf("%d",&n)!=EOF&&n!=-1){memset(que,0,sizeof(que));for(i=1;i<=150;i++)for(j=1;j<=150;j++)map[i][j]=INF;for(i=1;i<=150;i++)map[i][i]=0;scanf("%s%s%*c",place[1],place[2]);sum=2;for(i=1;i<=n;i++){flag=1;scanf("%s%*c",ch);for(j=1;j<=sum;j++)if(strcmp(place[j],ch)==0){flag=0;s=j;break;}if(flag){sum++;strcpy(place[sum],ch);s=sum;}flag=1;scanf("%s%*c",ch);for(j=1;j<=sum;j++)if(strcmp(place[j],ch)==0){flag=0;e=j;break;}if(flag){sum++;strcpy(place[sum],ch);e=sum;}scanf("%d",&cost);if(map[s][e]>cost)map[s][e]=map[e][s]=cost;}que[1]=1;for(i=1;i<=sum;i++)dis[i]=map[1][i];dis[1]=0;for(i=1;i<=sum;i++){min=INF;for(j=1;j<=sum;j++)if(!que[j]&&min>=dis[j]){min=dis[j];k=j;}que[k]=1;for(j=1;j<=sum;j++)if(!que[j]&&dis[j]>dis[k]+map[k][j])dis[j]=dis[k]+map[k][j];}if(strcmp(place[1],place[2])==0){printf("0\n");continue;}if(dis[2]==INF)printf("-1\n");elseprintf("%d\n",dis[2]);}return 0;
}
这篇关于HDU 2112——HDU Today的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
