UVA 11374 Airport Express（最短路）

最短路。

把题目抽象一下：已知一张图，边上的权值表示长度。现在又有一些边，只能从其中选一条加入原图，使起点->终点的距离最小。

当加上一条边a->b，如果这条边更新了最短路，那么起点st->终点ed的最小距离=st->a + a->b +b->ed 三个值的最短距离之和。于是正反求两次单元最短路。再将k条边遍历一遍就好了。

最近在改代码风格，写起来很别扭。。uva又挂了，最让我不理解的是http://www.cnblogs.com/arbitrary/archive/2013/02/06/2908099.html这个家伙的代码竟然能ac，问题是我稍微改一下就submission error，难道代码还能防盗= =

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<vector>
  4 #include<queue>
  5 #include<algorithm>
  6 #define clr(a,x) memset(a,x,sizeof(a));
  7 #define ref(i,a,b) for(int i=a;i<=b;i++)
  8 using namespace std;
  9 
 10 const int MAXN=1111;
 11 const int INF =55555;
 12 
 13 struct Edge{
 14     int u,v,c;
 15 };
 16 
 17 struct Node{
 18     int d,u;
 19     bool operator <(const Node x)const {
 20         return d>x.d;
 21     }
 22 };
 23 
 24 struct Dij{
 25     int n,m;
 26     vector<Edge>edge;
 27     vector<int>G[MAXN];
 28     bool vis[MAXN];
 29     int d[MAXN];
 30     int p[MAXN];
 31 
 32     void init(int n)
 33     {
 34         this->n=n;
 35         ref(i,0,n-1)G[i].clear();
 36         edge.clear();
 37     }
 38 
 39     void add(int u,int v,int c)
 40     {
 41         edge.push_back((Edge){u,v,c});
 42         m=edge.size();
 43         G[u].push_back(m-1);
 44     }
 45 
 46     void dij(int st)
 47     {
 48         priority_queue<Node>q;
 49         ref(i,0,n-1)d[i]=(i==st)?0:INF;
 50         clr(vis,0);
 51         q.push((Node){0,st});
 52         while(!q.empty())
 53         {
 54             Node x=q.top();
 55             q.pop();
 56             int u=x.u;
 57             if(vis[u])
 58                 continue;
 59             vis[u]=true;
 60             ref(i,0,G[u].size()-1){
 61                 Edge e=edge[G[u][i]];
 62                 if(d[e.v]>d[u]+e.c){
 63                     d[e.v]=d[u]+e.c;
 64                     p[e.v]=G[u][i];
 65                     q.push((Node){d[e.v],e.v});
 66                 }
 67             }
 68         }
 69     }
 70 };
 71 
 72 Dij solver;
 73 int d1[MAXN],d2[MAXN];
 74 int p[MAXN];
 75 
 76 int main()
 77 {
 78     int cnt=0;
 79     int n,m,k,st,ed;
 80     while(~scanf("%d%d%d",&n,&st,&ed))
 81     {
 82         if(cnt++)
 83             puts("");
 84 
 85         st--;ed--;
 86         solver.init(n);
 87 
 88         int u,v,c;
 89         scanf("%d",&m);
 90         ref(i,0,m-1){
 91             scanf("%d%d%d",&u,&v,&c);
 92             u--;v--;
 93             solver.add(u,v,c);
 94             solver.add(v,u,c);
 95         }
 96 
 97         solver.dij(st);
 98         ref(i,0,n-1)
 99             d1[i]=solver.d[i];
100 
101         solver.dij(ed);
102         ref(i,0,n-1){
103             d2[i]=solver.d[i];
104             p[i]=solver.p[i];
105         }
106         p[ed]=-1;
107 
108         scanf("%d",&k);
109         int s=d1[ed],a,b;
110         a=b=-1;
111         ref(i,0,k-1){
112             scanf("%d%d%d",&u,&v,&c);
113             u--;v--;
114             if(s>d1[u]+c+d2[v]){
115                 s=d1[u]+c+d2[v];
116                 a=u;b=v;
117             }
118             if(s>d1[v]+c+d2[u]){
119                 s=d1[v]+c+d2[u];
120                 a=v;b=u;
121             }
122         }
123         
124         int flog=0;
125         if(a==-1){       //不乘商务车
126             int x=st;
127 
128             while(x!=ed)
129             {
130                 if(!flog){printf("%d",x+1);flog=1;}
131                 else printf(" %d",x+1);
132                 x=solver.edge[p[x]].u;       //p[]中保存的是 u->v 这条边的序号
133             }
134             printf(" %d",ed+1);
135             printf("
Ticket Not Used
%d
",s);
136         }else{        //乘坐商务车
137             int x=st;
138             while(x!=a)
139             {
140                 if(!flog){printf("%d",x+1);flog=1;}
141                 else printf(" %d",x+1);
142                 x=solver.edge[p[x]].u;
143             }
144             if(x!=st)printf(" %d",x+1);
145             else printf("%d",x+1);
146             x=b;
147             while(x!=ed)
148             {
149                 printf(" %d",x+1);
150                 x=solver.edge[p[x]].u;
151             }
152             printf(" %d
",ed+1);
153             printf("%d
%d
",a+1,s);
154         }
155     }
156     return 0;
157 }
158 
159 /*
160 4 1 4
161 4
162 1 2 2
163 1 3 3
164 2 4 4
165 3 4 5
166 1
167 1 4 7
168 
169 2 1 2
170 1
171 1 2 2
172 1
173 1 2 1
174 */

View Code