题解：最短路，注意是无向图，而且有起点和终点相同的情况……
#include <iostream> #include <cstdio> #include <cstring> #include <utility> #include <queue> #include <map> using namespace std; const int N=20005; const int INF=9999999; typedef pair<int,int>seg;
map<string,int>mp; priority_queue<seg,vector<seg>,greater<seg> >q; int d[N],u[N],v[N],w[N],head[N],next[N],m,n,k,p,cnt,min; string begin,end,s; bool vis[N]; void build(){ memset(head,-1,sizeof(head)); for(int e=1;e<=m;e++){ cin>>s;u[e]=mp[s]?mp[s]:(mp[s]=++cnt); cin>>s;v[e]=mp[s]?mp[s]:(mp[s]=++cnt); scanf("%d",&w[e]); u[e+m]=v[e]; v[e+m]=u[e]; w[e+m]=w[e]; next[e]=head[u[e]]; head[u[e]]=e; next[e+m]=head[u[e+m]]; head[u[e+m]]=e+m; } } int Dijkstra(int src){ memset(vis,0,sizeof(vis)); for(int i=0;i<=cnt;i++)d[i]=INF; d[src]=0; q.push(make_pair(d[src],src)); while(!q.empty()){ seg now=q.top(); q.pop(); int x=now.second; if (vis[x]) continue; vis[x]=1; for(int e=head[x];e!=-1;e=next[e]) if(d[v[e]]>d[x]+w[e]){ d[v[e]]=d[x]+w[e]; q.push(make_pair(d[v[e]],v[e])); } } } int main(){ while(~scanf("%d",&m)){ if(m==-1)break; mp.clear(); cin>>begin>>end; mp[begin]=1; mp[end]=2; cnt=2; build(); if(begin==end){puts("0");continue;} Dijkstra(1); if (d[2]==INF) puts("-1"); else printf("%d ",d[2]); } return 0; }