【uva11374】Airport Express 最短路

题意：

　　在Iokh市中，机场快线是市民从市内去机场的首选交通工具。机场快线分为经济线和商业线两种，线路，速度和价钱都不同。你有一张商业线车票，可以坐一站商业线，而其他时候只能乘坐经济线。假设换乘时间忽略不计，你的任务是找一条去机场最快的路线。

分析：

　　因为商业线只能走一次，我们就枚举走哪条商业线（或不走），用2次单源最短路分别求从起点和终点出发到所有路的最短路，最后比较即可。

　　这里我最短路打的是spfa。

代码如下：（注意输出格式）

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<queue>
  7 using namespace std;
  8 #define Maxn 1010
  9 
 10 struct node
 11 {
 12     int x,y,c,next;
 13 }t[2*Maxn];int len;
 14 
 15 int n,s,e,m,k;
 16 int first[Maxn],dis[Maxn],d[Maxn];
 17 int td[Maxn],tds[Maxn];
 18 bool inq[Maxn];
 19 
 20 void ins(int x,int y,int c)
 21 {
 22     t[++len].x=x;t[len].y=y;t[len].c=c;
 23     t[len].next=first[x];first[x]=len;
 24 }
 25 
 26 void spfa(int s)
 27 {
 28     queue<int >     q;
 29     while(!q.empty()) q.pop();
 30     q.push(s);
 31     memset(dis,63,sizeof(dis));
 32     memset(inq,0,sizeof(inq));
 33     dis[s]=0;tds[s]=0;
 34     while(!q.empty())
 35     {
 36         int x=q.front();q.pop();
 37         for(int i=first[x];i;i=t[i].next)
 38         {
 39             int y=t[i].y;
 40             if(dis[y]>dis[x]+t[i].c)
 41             {
 42                 dis[y]=dis[x]+t[i].c;
 43                 tds[y]=x;
 44                 if(!inq[y]) {inq[y]=1;q.push(y);}
 45             }
 46         }
 47         inq[x]=0;
 48     }
 49 }
 50 
 51 void output(int x)
 52 {
 53     if(x==0) return;
 54     output(td[x]);
 55     if(td[x]!=0) printf(" "); 
 56     printf("%d",x);
 57 }
 58 
 59 int main()
 60 {
 61     int kase=0;
 62     while(scanf("%d%d%d",&n,&s,&e)!=EOF)
 63     {
 64         scanf("%d",&m);len=0;
 65         memset(first,0,sizeof(first));
 66         for(int i=1;i<=m;i++)
 67         {
 68             int x,y,c;
 69             scanf("%d%d%d",&x,&y,&c);
 70             ins(x,y,c);ins(y,x,c);
 71         }
 72         scanf("%d",&k);
 73         spfa(s);
 74         for(int i=1;i<=n;i++) d[i]=dis[i];
 75         for(int i=1;i<=n;i++) td[i]=tds[i];
 76         spfa(e);
 77         int ans=dis[s],ax,ay,ak;
 78         int ssum=1;
 79         for(int i=1;i<=k;i++)
 80         {
 81             int x,y,c;
 82             scanf("%d%d%d",&x,&y,&c);
 83             if(d[x]+dis[y]+c<ans) ax=x,ay=y,ans=d[x]+dis[y]+c,ssum=1;
 84             else if(d[x]+dis[y]+c==ans) ssum++;
 85             if(d[y]+dis[x]+c<ans) ax=y,ay=x,ans=d[y]+dis[x]+c;
 86             else if(d[y]+dis[x]+c==ans) ssum++;
 87         }
 88         if(kase!=0) printf("
");
 89         kase++;
 90         if(ans==dis[s])
 91         {
 92             printf("%d",s);
 93             for(int i=tds[s];i;i=tds[i]) printf(" %d",i);
 94             printf("
Ticket Not Used
");
 95         }
 96         else
 97         {
 98             output(ax);
 99             for(int i=ay;i;i=tds[i]) printf(" %d",i);
100             printf("
%d
",ax);
101         }
102         printf("%d
",ans);
103     }
104     return 0;
105 }

[uva11374]

2016-03-22 14:01:08