这是一道典型的最短路问题，直接用Dijkstra算法便可求解，主要是需要考虑输入的点是不是在已给出的地图中，具体看代码
#include<bits/stdc++.h>
#define MAX 1000000
using namespace std; int dis[];//记录每个点到起始点的距离
int edge[][];//邻接矩阵
void init(){
for(int i = ; i < ; i++){
for(int j = ; j < ; j++)edge[i][j] = MAX;//邻接矩阵初始化为MAX
}
}
int Dijkstra(int size, int start, int end){
int vertex[size];
memset(vertex, , sizeof(vertex));//判断是否在已确定距离的集合里 for(int i = ; i < size; i++){
dis[i] = (i == start ? : MAX);//起始点的距离权重为0，其他为MAX
} for(int i = ; i < size; i++){
int min_dis = MAX ;
int min_v; for(int j = ; j < size; j++){//寻找最小的距离点
if(!vertex[j] && dis[j] < min_dis){
min_dis = dis[j];
min_v = j;
}
} vertex[min_v] = ;//将其加入集合 for(int j = ; j < size; j++){//更新dis距离集合
dis[j] = min(dis[j], dis[min_v] + edge[min_v][j]);
}
} if(!vertex[end]) return -;
else return dis[end]; } int main(){
int t;
cin >> t;
while(t--){
init();
int edge_num;
cin >> edge_num;
string s1, s2;
int c;
map<string, int>_map;
int v_num = ;
while(edge_num--){
cin >> s1 >> s2;
if(_map.find(s1) == _map.end())_map[s1] = v_num++;
if(_map.find(s2) == _map.end())_map[s2] = v_num++;
int a = _map[s1];
int b = _map[s2];
cin >> edge[a][b];
edge[b][a] = edge[a][b];
} cin >> s1 >> s2; if(s1 == s2) cout << '' << endl;//假如两个地点相同，输出0
else if(_map.find(s1) == _map.end() || _map.find(s2) == _map.end()) {
cout << "-1" << endl;//假如有一个地点不在给出的路径中，输出-1
}
else {
int a = _map[s1];
int b = _map[s2];
cout << Dijkstra(v_num, a, b) << endl;//输出最短路
}
}
}