水题

#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
// #pragma comment(linker, "/STACK:102400000, 102400000")

using namespace std;

typedef pair<int, int> PLL;

const int N = 1010;
const int inf = 0x3f3f3f3f;
int head[N], tot;
int dist[N];
struct node
{
	int weight;
	int next;
	int to;
}edge[N * N];
struct node2
{
	int t;
	int len;
	char str[100];
}text[N];

void addedge(int from, int to, int weight)
{
	edge[tot].weight = weight;
	edge[tot].to = to;
	edge[tot].next = head[from];
	head[from] = tot++;
}

void dijkstra(int v0)
{
	priority_queue < PLL, vector<PLL>, greater<PLL> > qu;
	memset (dist, inf, sizeof(dist));
	dist[v0] = 0;
	qu.push(make_pair(dist[v0], v0));
	while (!qu.empty())
	{
		PLL tmp = qu.top();
		qu.pop();
		int u = tmp.second;
		for (int i = head[u]; ~i; i = edge[i].next)
		{
			int v = edge[i].to;
			if (dist[v] > dist[u] + edge[i].weight)
			{
				dist[v] = dist[u] + edge[i].weight;
				qu.push(make_pair(dist[v], v));
			}
		}
	}
}

int main()
{
	int n;
	while(~scanf("%d", &n), n)
	{
		memset (head, -1, sizeof(head));
		tot = 0;
		for (int i = 0; i < n; ++i)
		{
			scanf("%d%s", &text[i].t, text[i].str);
			int len = strlen(text[i].str);
			text[i].len = len;
		}
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if (i == j)
				{
					continue;
				}
				int len = text[i].len;
				if (text[i].str[len - 1] == text[j].str[3] && text[i].str[len - 2] == text[j].str[2] && text[i].str[len - 3] == text[j].str[1] && text[i].str[len - 4] == text[j].str[0])
				{
					addedge(i, j, text[i].t);
				}
			}
		}
		dijkstra(0);
		if (dist[n - 1] == inf)
		{
			printf("-1\n");
		}
		else
		{
			printf("%d\n", dist[n - 1]);
		}
	}
	return 0;
}