Dijkstra部分不难，主要是建图

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
#define INF 10000000
#define maxn 1005
struct bian
{
    string a;
    string b;
    int time;
}tu[maxn];
int n,s[maxn],dist[maxn];
int edge[maxn][maxn];
void Dijkstra(int v0)
{
    int i,j;
    for(i=0;i<n;i++)
    {
        s[i]=0;dist[i]=edge[v0][i];
    }
    s[v0]=1;dist[v0]=0;
    for(i=0;i<n-1;i++)
    {
        int min=INF,u=v0;
        for(j=0;j<n;j++)
        {
            if(!s[j]&&dist[j]<min)
            {
                u=j;
                min=dist[j];
            }
        }
        s[u]=1;
        for(j=0;j<n;j++)
        {
            if(!s[j]&&dist[j]>dist[u]+edge[u][j])
            dist[j]=dist[u]+edge[u][j];
        }
    }
}
int main()
{
    int i,j,k,t;
    string str;
    while(cin>>n)
    {
        if(n==0) break;
        for(k=0;k<n;k++)//预处理
        {
            cin>>t>>str;
            tu[k].time=t;
            tu[k].a="";
            tu[k].b="";
            for(j=0;j<4;j++)
            {
                tu[k].a+=str[j];
            }
            for(j=str.length()-4;j<str.length();j++)
            {
                tu[k].b+=str[j];
            }
        }//建图
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                edge[i][j]=INF;
                if(i==j) continue;
                if(tu[i].b==tu[j].a) edge[i][j]=tu[i].time;
            }
        }
        Dijkstra(0);
        if(dist[n-1]<INF) cout<<dist[n-1]<<endl;
        else cout<<-1<<endl;
    }
    return 0;
}