idiomatic phrases game(最短路).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

#define Inf 0xfffffff
int n,t;
int spos,tpos;
int matrix[1100][1100];
char idiom[1100][5];

inline int get_pos(char *p, int total)
{
	int i;
	for (i=1;i<total;i++) {
		if (strcmp(idiom[i], p)==0) {
			return i;
		}
	}
	return -1;
}

int Dijkstra(int x,int y)     //起点Vx 终点Vy
{
	int i,j,k,mark[2100];
	int min,dist[2100];
	if (x == y) {
		return 0;
	}
	for(i=1;i<=n;i++) {
		mark[i] = 0;
		dist[i] = matrix[x][i];
	}
	mark[x] = 1;
	do {
		min=Inf;
		k=0;
		for(i=1;i<=n;i++)
			if(dist[i]!=-1 && mark[i]==0 && dist[i]<min) {
				min = dist[i];
				k = i;
			}
			if(k) {
				mark[k] = 1;
				for(i=1;i<=n;i++)
					if (matrix[k][i] != -1) {
						if(dist[i]==-1 || min+matrix[k][i]<dist[i]) {
							dist[i] = min + matrix[k][i];
						}
					}
			}
		if(k == y)	return dist[y];
	}while(k);
	return dist[y];
}

int main()
{
	int i,j,wpos1,wpos2,ws,c1,c2,ans;
	char str[1100],word[5];
	
	while (scanf("%d",&n), n) {
		ws = 1;
		memset(matrix, -1,sizeof(matrix));
		word[4] = 0;
		for (i=0;i<n;i++) {
			scanf("%d %s",&t,str);
			for (j=0;j<4;j++) {
				word[j] = str[j];
			}
			wpos1 = get_pos(word,ws);
			if (wpos1==-1) {
				wpos1 = ws;
				strcpy(idiom[ws], word);
				ws ++;
			}
			int len = strlen(str);
			for (j=0;j<4;j++) {
				word[j] = str[ len-4+j ];
			}
			wpos2 = get_pos(word,ws);
			if (wpos2==-1) {
				wpos2 = ws;
				strcpy(idiom[ws], word);
				ws ++;
			}
			if (matrix[wpos1][wpos2] == -1) {
				matrix[wpos1][wpos2] = t;
			}
			else {
				matrix[wpos1][wpos2] = matrix[wpos1][wpos2] > t ? t : matrix[wpos1][wpos2] ;
			}
			if (i == 0) {
				spos = wpos2;
				c1 = t;
			}
			else if (i == n-1) {
				tpos = wpos1;
			}
		}//read and make graph

		n = ws-1;
		ans = Dijkstra(spos, tpos);
		if (ans == -1) {
			printf("-1\n");
		}
		else {
			printf("%d\n", ans + c1);
		}
	}
}