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;
}
View Code

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。