枚举+最短路
题意是说出发地 和 目的地 之间有一条边是免费的。问你最小费用。
误区：求出最短路-路径中的最大边。（有些其他边免费之后，可能最短路就变了）
正确思路：枚举每条边，将其费用设为0.然后求最短路。找费用最小。
这是无向图，至于地名可以用map映射。
#include #include #include #include #include #include #include #include #include #include #include #define INF 0x7fffffff #define eps 1e-6 #define LL long long using namespace std; int n,m; map city; struct lx { int v,len; }; vector g[501]; int x,y,ans; struct edge { int u,v; }; void SPFA(edge flag) { queue q; bool vis[501]; int dis[501]; for(int i=0; i<501; i++) dis[i]=INF,vis[i]=0; dis[x]=0; vis[x]=1; q.push(x); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int j=0; j dis[u]+len) { dis[v]=dis[u]+len; if(!vis[v]) { vis[v]=1; q.push(v); } } } } ans=min(ans,dis[y]); } int main() { char a[11],b[11]; while(scanf("%s%s",a,b)!=EOF) { city.clear(); for(int i=0; i<501; i++) g[i].clear(); int u,v,len,cot=1; x=city[a]; if(x==0) { city[a]=cot++; x=cot-1; } y=city[b]; if(y==0) { city[b]=cot++; y=cot-1; } scanf("%d",&m); queue que; for(int i=0; i