结点名是字符串的最短路，处理好了用dijkstra即可
自己写了个非常丑陋的处理……起点和终点是同一点的时候还得判断。
#include <stdio.h>
#include <string.h>
#define INF 999999999
#define MAX 155
int N,map[MAX][MAX],stationnum;
char station[MAX][35];
int input(){
int j;
char stationname[35];
scanf("%s",stationname);
for(j = 0; j < stationnum; j++)
if(!strcmp(stationname,station[j]))
return j;
strcpy(station[stationnum],stationname);
stationnum++;
return stationnum - 1;
}
int dijkstra(int start,int end){
bool hash[MAX];
int i,min,path[MAX],laststr;
for(i = 0; i <= stationnum; i++){
hash[i] = true;
path[i] = INF;
}
hash[start] = false;
path[start] = 0;
while(start != end){
laststr = start;
for(i = 0; i <= stationnum; i++)
if(map[start][i])
if(path[i] > path[start] + map[start][i])
path[i] = path[start] + map[start][i];
min = INF;
for(i = 0; i <= stationnum; i++)
if(min > path[i] && hash[i]){
min = path[i];
start = i;
}
hash[start] = false;
if(min == INF)
return -1;
}
return path[1];
}
int main(void){
int i,a,b,t,skip;
while(1){
memset(map,0,sizeof(map));
skip = 0;
stationnum = 2;
scanf("%d",&N);
if(N == -1)
break;
scanf("%s%s",station[0],station[1]);
if(!strcmp(station[0],station[1]))
skip = 1;
for(i = 0; i < N; i++){
a = input();
b = input();
scanf("%d",&t);
if(map[a][b] == 0)
map[a][b] = map[b][a] = t;
else if(map[a][b] > t)
map[a][b] = map[b][a] = t;
}
if(skip)
printf("0\n");
else
printf("%d\n",dijkstra(0,stationnum));
}
return 0;
}