我他喵的早就想好过了这道题之后的动作了 UVA11374
我他喵的早就想好过了这道题之后的动作了，他妈的使劲敲桌子
，原来是这个错误！！！
每次提交查找，我他喵的连这个题号都记得滾瓜烂熟了。。。
题意：
在Iokh市中，机场快线是市民从市内去机场的首选交通工具。机场快线分为经济线和商业线两种，线路，速度和价钱都不同。你有一张商业线车票，可以做一站商业线，而其他时候只能乘坐经济线。假设换乘时间忽略不计，你的任务是找一条去机场最快的路线。。
分析:枚举商业线T(a,b),则总时间为f(a)+T(a,b)+g(b);f和g用两次dijkstra来计算，以S为起点的dijkstra和以E为起点的dijkstra；
一开始我是每读一条VIP路线更新一次，果断TLE
后来正确理解f(a)+T(a,b)+g(b)这个式子后就无限的WA了
最后坚持了几天，感觉自己思路实在是没问题啊，就找了分标程参考了一下。
他喵的，我忘了每次初始化调用 init()了
还有UVA上对每组数据之间的换行不报PE报WA
还有读VIP路线时，自己忘考虑双向了，脑袋不够用啊。。。
还有自己的模板没调用DIJKSTRS结构体一样适用。
#include <iostream>#include <cstdio>#include <cstring>#include <vector>#include <queue>using namespace std;const int maxn=50000;const int INF=1000000000;struct Edge{int from,to,dist;};struct Node{ int d,u; bool operator <(const Node a) const { return a.d<d; }};int n,m;int d[maxn];int p1[maxn],p2[maxn];bool done[maxn];int dis[maxn];vector<int> G[maxn];vector<Edge> edges;int f1[maxn],f2[maxn];//起点到每个点x的最短路和x到终点的最短路int eco_num,vip_num,x[maxn],y[maxn],z[maxn];int t1[maxn],t2[maxn],t3[maxn];//vip路线void init(){ for(int i=0;i<n;i++) G[i].clear(); edges.clear();}void addedge(int from,int to,int dist){ edges.push_back((Edge){from,to,dist}); int temp=edges.size(); G[from].push_back(temp-1);}void dijk(int s,int ok){ priority_queue<Node> q; for(int i=0;i<n;i++) d[i]=INF; d[s]=0; memset(done,0,sizeof(done)); q.push((Node){0,s}); while(!q.empty()) { Node x=q.top(); q.pop(); int u=x.u; if(done[u]) continue; done[u]=true; for(int i=0;i<G[u].size();i++) { Edge &e=edges[G[u][i]]; if(d[e.to]>d[u]+e.dist) { d[e.to]=d[u]+e.dist; //p[e.to]=G[u][i];//这个指的是前一条边。。。 if(ok==1) p1[e.to]=u; else p2[e.to]=u; q.push((Node){d[e.to],e.to}); } } }}int main(){ int s,e,a,b,c,kcase=0;//起点终点 while(scanf("%d%d%d",&n,&s,&e)!=EOF) { if(kcase!=0) printf("\n");//每次都要输出换行符 注意题干 kcase++; init();//初始化。。。 scanf("%d",&eco_num); for(int i=0;i<eco_num;i++) { scanf("%d%d%d",&x[i],&y[i],&z[i]); addedge(x[i]-1,y[i]-1,z[i]); addedge(y[i]-1,x[i]-1,z[i]); } dijk(s-1,1);//调用两次Dijkstra就足够。 int min=d[e-1]; for(int i=0;i<n;i++) f1[i]=d[i]; dijk(e-1,2); for(int i=0;i<n;i++) f2[i]=d[i]; scanf("%d",&vip_num); int vip_input=-1,vip_output=-1; for(int i=0;i<vip_num;i++) { scanf("%d%d%d",&a,&b,&c); a--;b--; if(f1[a]+f2[b]+c<min) //还有这地方一开始老是以为只有单向 { min=f1[a]+f2[b]+c; vip_input=a; vip_output=b; } if(f2[a]+f1[b]+c<min) { min=f2[a]+f1[b]+c; vip_input=b; vip_output=a; } } if(vip_input==-1&&vip_output==-1) //各种输出都要加1 { int cnt=0; memset(dis,0,sizeof(dis)); int pp=e-1; while(pp!=s-1) { dis[cnt++]=pp; pp=p1[pp]; } printf("%d",s); for(int i=cnt-1;i>=0;i--) { printf(" %d",dis[i]+1); } printf("\n"); } else { int cnt=0; memset(dis,0,sizeof(dis)); int pp=vip_input; while(pp!=s-1) { dis[cnt++]=pp; pp=p1[pp]; } printf("%d ",s); for(int i=cnt-1;i>=0;i--) printf("%d ",dis[i]+1); cnt=0; memset(dis,0,sizeof(dis)); pp=vip_output; while(pp!=e-1) { dis[cnt++]=pp; pp=p2[pp]; } for(int i=0;i<cnt;i++) printf("%d ",dis[i]+1); printf("%d\n",e); } if(vip_input==-1&&vip_output==-1) printf("Ticket Not Used\n"); else printf("%d\n",vip_input+1); printf("%d\n",min); } return 0;}