C :

#include<stdio.h>
#include<string.h>

const int inf=1000000000;

int n,g[1000][1000],min[1000];

void dijkstra(int s)
{
	int v[1000],i,j,k;
	for(i=0;i<n;i++)
	{
		min[i]=inf;
		v[i]=0;
	}
	for(min[s]=0,j=0;j<n;j++)
	{
		for(k=-1,i=0;i<n;i++)
			if(!v[i]&&(k==-1||min[i]<min[k]))
				k=i;
		for(v[k]=1,i=0;i<n;i++)
			if(!v[i]&&min[k]+g[k][i]<min[i])
				min[i]=min[k]+g[k][i];
	}
}

int main()
{
	int t,i,j,l,time[1000];
	char s[200],head[1000][5],tail[1000][5];
	while(scanf("%d",&n)!=EOF,n)
	{
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				g[i][j]=inf;
		for(i=0;i<n;i++)
		{
			scanf("%d%s",&t,s);
			l=strlen(s);
			head[i][0]=s[0];
			head[i][1]=s[1];
			head[i][2]=s[2];
			head[i][3]=s[3];
			head[i][4]='\0';
			tail[i][3]=s[l-1];
			tail[i][2]=s[l-2];
			tail[i][1]=s[l-3];
			tail[i][0]=s[l-4];
			tail[i][4]='\0';
			time[i]=t;
		}
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				if(!strcmp(tail[i],head[j]))
					g[i][j]=time[i];
		dijkstra(0);
		if(min[n-1]==inf)
			printf("-1\n");
		else
			printf("%d\n",min[n-1]);
	}
	return 0;
}

C++ :

#include<stdio.h>
#include<string.h>

const int inf=1000000000;

int n,g[1000][1000],min[1000];

void dijkstra(int s)
{
	int v[1000],i,j,k;
	for(i=0;i<n;i++)
	{
		min[i]=inf;
		v[i]=0;
	}
	for(min[s]=0,j=0;j<n;j++)
	{
		for(k=-1,i=0;i<n;i++)
			if(!v[i]&&(k==-1||min[i]<min[k]))
				k=i;
		for(v[k]=1,i=0;i<n;i++)
			if(!v[i]&&min[k]+g[k][i]<min[i])
				min[i]=min[k]+g[k][i];
	}
}

int main()
{
	int t,i,j,l,time[1000];
	char s[200],head[1000][5],tail[1000][5];
	while(scanf("%d",&n)!=EOF,n)
	{
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				g[i][j]=inf;
		for(i=0;i<n;i++)
		{
			scanf("%d%s",&t,s);
			l=strlen(s);
			head[i][0]=s[0];
			head[i][1]=s[1];
			head[i][2]=s[2];
			head[i][3]=s[3];
			head[i][4]='\0';
			tail[i][3]=s[l-1];
			tail[i][2]=s[l-2];
			tail[i][1]=s[l-3];
			tail[i][0]=s[l-4];
			tail[i][4]='\0';
			time[i]=t;
		}
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				if(!strcmp(tail[i],head[j]))
					g[i][j]=time[i];
		dijkstra(0);
		if(min[n-1]==inf)
			printf("-1\n");
		else
			printf("%d\n",min[n-1]);
	}
	return 0;
}

Java :

import java.util.*;
public class Main {
	private static Scanner in;
	static String[] head = new String[1000];//记录一个成语的头
	static String[] tail = new String[1000];//记录一个成语的尾
	static int[] time = new int[1000];//记录一个成语找到下一个成语的时间
	static int[][] g = new int[1000][1000];//记录第i个成语找到第j个成语的时间
    static int[] min = new int [1000];
    static int n;
	public static void main(String[] args) {
		in = new Scanner(System.in);
		int len,i,k,h;
		String str;
		//对于每一组测试数据
		while(in.hasNext()) {
			n=in.nextInt();
			if(n==0) break;
			for( i=0;i<n;i++) {
				time[i]=in.nextInt();
				str=in.next();
				len=str.length();
				head[i]="" + str.charAt(0)+str.charAt(1)+str.charAt(2)+str.charAt(3);
				tail[i]="" + str.charAt(len-4)+str.charAt(len-3)+str.charAt(len-2)+str.charAt(len-1);
			}
			//记录第i个成语找到第j个成语的时间
		
			for(k=0;k<n;k++) {
				for( h=0;h<n;h++) {
					if((head[k].equals(tail[h]))){
						g[h][k]=time[h];
					}
					else {
						g[h][k] = 1000000000;
					}		
				}
			}
			//调用Dijkstra最短路径算法
			dist();
			if(min[n-1]==1000000000){
				System.out.println(-1);
			}
			else {
			System.out.println(min[n-1]);
			}
		}
	}
	public static void dist(){
		int[] v=new int[n]; 
		int d,k,i,j,h;
		for(i=0;i<n;i++) {
			min[i]=1000000000;
			v[i]=0;
		}
		min[0]=0;
		//每一次循环，加入一个结点到v
		for(j=0;j<n;j++) {
			//找出从第一个成语到下一个成语的最短路径
			for(d=-1,k=0;k<n;k++) 
				if(v[k]==0&&(d==-1||min[k]<min[d])) {
					d=k;
				}
		   //更新与d直接相邻顶点的dist值
			for(v[d]=1,h=0;h<n;h++) {
				if(v[h]==0&&((min[d]+g[d][h])<min[h])){
					min[h]=min[d]+g[d][h];
				}
			}
			}
		}
	}