在刘汝佳的那本书上看到了这道题，思路：先预处理出起点到所有点以及终点到所有点的最短路径，然后就是枚举所有的商务边，因为只能有一条商务边，所以最优的路径肯定要么就是起点->商务边起点->商务边终点->终点，要么就是直接起点->终点。时间复杂度为预处理的mlogn加上k次枚举。最后还要递归输出路径。
代码如下，UVA的输出有毒，一直过不了，但肯定是对的。
//不知道是怎么回事，可能是输出格式的问题。 #include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; struct node{ int nxt,to,val; }edge[maxn*3]; int head[maxn],cnt; int dis[maxn],dis1[maxn]; int ans; inline void add(int x,int y,int v){ edge[++cnt].nxt=head[x]; edge[cnt].to=y; edge[cnt].val=v; head[x]=cnt; } int n,s,e,m,k,x,y,z; int o,p,t; bool vis[maxn],vis1[maxn]; int pre1[maxn],pre2[maxn]; int ljb; priority_queue< pair<int,int> >q; inline void dijkstra(int x){ memset(dis,0x3f3f3f3f,sizeof(dis)); q.push(make_pair(0,x)); dis[x]=0; while(q.size()!=0){ int u=q.top().second; q.pop(); if(vis[u]) continue; vis[u]=true; for(int i=head[u];i;i=edge[i].nxt){ int s=edge[i].to; if(dis[u]+edge[i].val<dis[s]){ pre1[s]=u; dis[s]=dis[u]+edge[i].val; q.push(make_pair(-dis[s],s)); } } } } priority_queue< pair<int,int> >q1; inline void dijkstra2(int x){ memset(dis1,0x3f3f3f3f,sizeof(dis1)); q1.push(make_pair(0,x)); dis1[x]=0; while(q1.size()!=0){ int u=q1.top().second; q1.pop(); if(vis1[u]) continue; vis1[u]=true; for(int i=head[u];i;i=edge[i].nxt){ int v=edge[i].to; if(dis1[v]>dis1[u]+edge[i].val){ pre2[v]=u; dis1[v]=dis1[u]+edge[i].val; q1.push(make_pair(-dis1[v],v)); } } } } void print1(int x){ if(x==s){ printf("%d",x); return; } print1(pre1[x]); printf(" %d",x); } void print2(int x){ if(!x) return; printf(" %d",x); print2(pre2[x]); } int main(){ while(scanf("%d%d%d",&n,&s,&e)!=EOF){ if(ljb==1) printf(" "),ljb=0; memset(edge,0,sizeof(edge)); memset(head,0,sizeof(head)); memset(vis,0,sizeof(vis)); memset(vis1,0,sizeof(vis1)); memset(pre2,0,sizeof(pre2)); memset(pre1,0,sizeof(pre1)); cnt=0; scanf("%d",&m); for(register int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z);add(y,x,z); } dijkstra(s); ans=dis[e]; dijkstra2(e); scanf("%d",&k); int l=0,r=0; for(register int i=1;i<=k;i++){ scanf("%d%d%d",&o,&p,&t); int s1=dis[o]+dis1[p]+t; int s2=dis[p]+dis1[o]+t; if(ans>s1){ ans=s1; l=o;r=p; } if(ans>s2){ ans=s2; l=p;r=o; } } if(l==0){ print1(s); printf(" Ticket Not Used %d ",ans); } else{ print1(l);print2(r); printf(" %d %d ",l,ans); } ljb=1; } return 0; }