HDU 1546 Idiomatic Phrases Game(最短路,Dijsktra,理解题意很重要)
1.注意因为要判断能不能到达,所以要在模版里面判断k有没有更新。
2.看懂题目意思和案例的解法很重要。
#define _CRT_SECURE_NO_WARNINGS //题目大意:现要进行单词接龙,要求前一个单词的最后四个字符和后一个单词的前四个字符相同, //给你一串单词,并给出由当前单词找到下一个单词所需花费的时间, //然后求由第一个单词找到最后一个单词所需的最短时间 //思路:最短路,如果一个单词的最后四个字符和下一个单词的前四个字符相同, //则在两个单词间连一条有向边,边的权值为第一个单词所需的花费时间,则转换为了图, //求第一个单词到最后一个单词的最短路,Dijksta算法 #include<string.h> #include<stdio.h> #include<math.h> #include<algorithm> using namespace std; const int MAXN=1010; #define typec int const typec INF=0x3f3f3f3f;//防止后面溢出,这个不能太大 bool vis[MAXN]; typec cost[MAXN][MAXN],a[MAXN]; typec lowcost[MAXN]; void Dijkstra(int n,int beg) { for(int i=1;i<=n;i++) { lowcost[i]=cost[beg][i];vis[i]=false; } for(int i=1;i<=n;i++) { typec temp=INF; int k=-1; for(int j=1;j<=n;j++) if(!vis[j]&&lowcost[j]<temp) { temp=lowcost[j]; k=j; } if(k!=-1){ vis[k]=true; for(int l=1;l<=n;l++) if(!vis[l]) if(lowcost[l]>lowcost[k]+cost[k][l]) lowcost[l]=lowcost[k]+cost[k][l]; } } } int main() { int n,i,j,len; char b[MAXN][250],c[MAXN][5],d[MAXN][5]; while(scanf("%d",&n),n) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) cost[i][j]=(i==j)? 0:INF; for(i=1;i<=n;i++) { scanf("%d%s",&a[i],b[i]); len=strlen(b[i]); c[i][0]=b[i][0],c[i][1]=b[i][1],c[i][2]=b[i][2],c[i][3]=b[i][3];c[i][4]=‘\0‘; d[i][0]=b[i][len-4],d[i][1]=b[i][len-3],d[i][2]=b[i][len-2],d[i][3]=b[i][len-1];d[i][4]=‘\0‘; for(j=1;j<i;j++) { if(strcmp(d[i],c[j])==0) if(cost[i][j]>a[i]) cost[i][j]=a[i]; if(strcmp(d[j],c[i])==0) if(cost[j][i]>a[j]) cost[j][i]=a[j]; } } Dijkstra(n,1); if(lowcost[n]==INF) printf("-1\n"); else printf("%d\n",lowcost[n]); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。