hdu 2112

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
const int N=160, inf=1000000000;
int road[N][N], dis[N], vis[N];
int n,m,s,f;

void Dijkstra()
{
    int i,j,k,tmp;
    memset(vis,0,sizeof(vis));
    for(i=1;i<=n;i++)
        dis[i]=road[s][i];
    dis[s]=0; vis[s]=1;
    for(i=1;i<n;i++)
    {
        tmp=inf, k=s;
        for(j=1;j<=n;j++)
        {
            if( vis[j]==0 && tmp>dis[j] )
            {
                tmp=dis[j];
                k=j;
            }
        }
        vis[k]=1;
        for(j=1;j<=n;j++)
        {
            tmp=dis[k]+road[k][j];
            if( vis[j]==0 && dis[j]>tmp )
                dis[j]=tmp;
        }
    }
    if( dis[f]==inf )
        printf("-1\n");
    else
        printf("%d\n",dis[f]);
}

int main()
{
    // freopen("cin","r",stdin);
    int i,j,cost;
    char a[31], b[31], start[31], end[31];
    while( scanf("%d",&m) && m!=-1 )
    {
        map<string,int> v; 
        scanf("%s %s",start,end);
        v[start]=1, v[end]=2;
        for(i=1;i<=151;i++)
        {
            for(j=1;j<=151;j++)
                road[i][j]=inf;
        }
        for(i=0, n=2; i<m; i++)
        {
            scanf("%s %s %d",a, b, &cost);
            if( v[a]==0 ) v[a]=++n;
            if( v[b]==0 ) v[b]=++n;
            road[v[a]][v[b]]=road[v[b]][v[a]]=cost;

            if( road[v[a]][v[b]]>cost )
                road[v[a]][v[b]]=road[v[b]][v[a]]=cost;

        }
        s=v[start]; f=v[end];
        Dijkstra();
    }
    return 0;
}