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=;

#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=;i<=n;i++)

    {

        lowcost[i]=cost[beg][i];vis[i]=false;

    }

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

    {

        typec temp=INF;

        int k=-;

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

            if(!vis[j]&&lowcost[j]<temp)

            {

                temp=lowcost[j];

                k=j;

            }

            if(k!=-){

                vis[k]=true;

                for(int l=;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][],c[MAXN][],d[MAXN][];

    while(scanf("%d",&n),n)

    {

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

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

                cost[i][j]=(i==j)? :INF;

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

        {

            scanf("%d%s",&a[i],b[i]);

            len=strlen(b[i]);

            c[i][]=b[i][],c[i][]=b[i][],c[i][]=b[i][],c[i][]=b[i][];c[i][]='\0';

            d[i][]=b[i][len-],d[i][]=b[i][len-],d[i][]=b[i][len-],d[i][]=b[i][len-];d[i][]='\0';

            for(j=;j<i;j++)

            {

                if(strcmp(d[i],c[j])==)

                    if(cost[i][j]>a[i])

                        cost[i][j]=a[i];

                if(strcmp(d[j],c[i])==)

                    if(cost[j][i]>a[j])

                        cost[j][i]=a[j];

            }

        }

        Dijkstra(n,);

        if(lowcost[n]==INF)

            printf("-1\n");

        else

            printf("%d\n",lowcost[n]);

    }

    return ;

}