B-dijkstra-TT的旅行日记

题意:

众所周知,TT 有一只魔法猫。

今天他在 B 站上开启了一次旅行直播,记录他与魔法猫在喵星旅游时的奇遇。 TT 从家里出发,准备乘坐猫猫快线前往喵星机场。猫猫快线分为经济线和商业线两种,它们的速度与价钱都不同。当然啦,商业线要比经济线贵,TT 平常只能坐经济线,但是今天 TT 的魔法猫变出了一张商业线车票,可以坐一站商业线。假设 TT 换乘的时间忽略不计,请你帮 TT 找到一条去喵星机场最快的线路,不然就要误机了!

输入

输入包含多组数据。

每组数据第一行为 3 个整数 N, S 和 E (2 ≤ N ≤ 500, 1 ≤ S, E ≤ 100),即猫猫快线中的车站总数,起点和终点(即喵星机场所在站)编号。

下一行包含一个整数 M (1 ≤ M ≤ 1000),即经济线的路段条数。

接下来有 M 行,每行 3 个整数 X, Y, Z (1 ≤ X, Y ≤ N, 1 ≤ Z ≤ 100),表示 TT 可以乘坐经济线在车站 X 和车站 Y 之间往返,其中单程需要 Z 分钟。

下一行为商业线的路段条数 K (1 ≤ K ≤ 1000)。

接下来 K 行是商业线路段的描述,格式同经济线。

所有路段都是双向的,但有可能必须使用商业车票才能到达机场。保证最优解唯一。

输出

对于每组数据,输出3行。第一行按访问顺序给出 TT 经过的各个车站(包括起点和终点),第二行是 TT 换乘商业线的车站编号(如果没有使用商业线车票,输出"Ticket Not Used",不含引号),第三行是 TT 前往喵星机场花费的总时间。

本题不忽略多余的空格和制表符,且每一组答案间要输出一个换行

输入样例

4 1 4
4
1 2 2
1 3 3
2 4 4
3 4 5
1
2 4 3

输出样例

1 2 4
25

My Solution:

本题商业线的引入使得问题变得复杂化,如果没有商业线,则问题变成了简单的图问题中的最短路问题。

我们发现加入商业线以后有两种做法,最短路中包含一条商业线或者不包含商业线。

对于不包含商业线的情况,我们可以求一个最短路。

对于包含商业线的情况,因为只走一条商业线,我们可以枚举每一条商业线的情况,然后取最小。

接下来,对于走(一条)商业线的问题怎么求短路呢?

分别从起点和终点跑一次最短路,然后取两次的最小值

min (dis1[u]+dis2[v]+w , dis1[v]+dis2[u]+w ) 

最后合并以上 以上情况,取最小即可!



  1 #include<iostream>
  2 #include<string.h>
  3 #include<algorithm> 
  4 using namespace std;
  5 const int maxn=1000010;
  6 int n,m,k,s,e,tot,ans=10000000,sum;
  7 int head[maxn],dis1[maxn],dis2[maxn];
  8 int pre1[maxn],pre2[maxn];
  9 int p[maxn],a[maxn];
 10 bool flag[maxn];
 11 int ans_u,ans_v,ans_w;
 12 struct node
 13 {
 14     int v;
 15     int w;
 16     int next;
 17 }e1[maxn];
 18 void add_edge(int u,int v,int w)
 19 {
 20     e1[++tot].v=v;
 21     e1[tot].w=w;
 22     e1[tot].next=head[u];
 23     head[u]=tot;
 24 }
 25 
 26 void dijkstra(int u,int *dis,int *pre)
 27 {
 28     memset(flag,0,sizeof(flag));
 29     for(int i=1;i<=n;i++)
 30     dis[i]=maxn;
 31     dis[u]=0;
 32     for(int i=1;i<=n;i++)
 33     {
 34         int k=0,minn=maxn;
 35         for(int j=1;j<=n;j++)
 36         if(!flag[j]&&dis[j]<minn)
 37         {
 38             minn=dis[j];
 39             k=j;
 40         }
 41         flag[k]=1;
 42         for(int j=head[k];j;j=e1[j].next)
 43         if(!flag[e1[j].v]&&dis[e1[j].v]>dis[k]+e1[j].w) //松弛 
 44         {
 45             dis[e1[j].v]=dis[k]+e1[j].w;
 46             pre[e1[j].v]=k;
 47         }
 48     }
 49 }
 50 int main()
 51 {
 52     int x,y,z,u,v,w;
 53     cin>>n>>s>>e; 
 54     while(1)
 55     {
 56         memset(flag,0,sizeof(flag));
 57         memset(pre1,0,sizeof(pre1));
 58         memset(pre2,0,sizeof(pre2));
 59         memset(head,0,sizeof(head));
 60         memset(a,0,sizeof(a));
 61         tot=0;
 62         cin>>m;
 63         ans_u=0;sum=0;
 64         for(int i=1;i<=m;i++)
 65         {
 66             cin>>x>>y>>z;
 67             add_edge(x,y,z);
 68             add_edge(y,x,z);
 69         }
 70         
 71         dijkstra(s,dis1,pre1) ;
 72         dijkstra(e,dis2,pre2) ;
 73         
 74         cin>>k;
 75         int ans=dis1[e];
 76         for(int i=1;i<=k;i++)
 77         {
 78             cin>>u>>v>>w;
 79             if(dis1[u]+dis2[v]+w<ans)
 80             {
 81                 ans=dis1[u]+dis2[v]+w;
 82                 ans_u=u;
 83                 ans_v=v;
 84             }
 85             if(dis2[u]+dis1[v]+w<ans)//再次更新 
 86             {
 87                 ans=dis2[u]+dis1[v]+w;
 88                 ans_u=v;
 89                 ans_v=u;
 90             }
 91         }
 92         int tmp;
 93         if(ans_u==0)//不需要商务线 
 94         {
 95             tmp=e;
 96             while(tmp)
 97             {
 98                 a[++sum]=tmp;
 99                 if(tmp==s) break;
100                 tmp=pre1[tmp];
101             }
102             for(int i=sum;i>=2;i--) cout<<a[i]<<" ";
103             cout<<a[1]<<endl;
104             cout<<"Ticket Not Used"<<endl<<ans<<endl;
105         }
106         else//需要商务线 
107         {
108             tmp=ans_v;
109             while(tmp)
110             {
111                 a[++sum]=tmp;
112                 if(tmp==e) break;
113                 tmp=pre2[tmp];
114             }
115             for(int i=1;i<=sum/2;i++)
116             swap(a[i],a[sum-i+1]);
117             tmp=ans_u;
118             while(tmp)
119             {
120                 a[++sum]=tmp;
121                 if(tmp==s) break;
122                 tmp=pre1[tmp];
123             }
124             for(int i=sum;i>=2;i--) cout<<a[i]<<" ";
125             cout<<a[1]<<endl;
126             cout<<ans_u<<endl<<ans<<endl;
127         }
128         
129         if(cin>>n>>s>>e)
130             cout<<endl;     //每个输出换行 
131         else 
132             break;
133     }
134     return 0;
135 }

 



 

上一篇:高精度求大数乘法


下一篇:Repeating Decimals UVA - 202---求循环部分