本文共 2523 字,大约阅读时间需要 8 分钟。
众所周知,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 前往喵星机场花费的总时间。 本题不忽略多余的空格和制表符,且每一组答案间要输出一个换行 换个思路理解本题,你是一个司机上面这一大堆题目,其实就要告诉你:N个车站 S-起点 E-终点从起点到终点有 经济线 商业线 两种线路M条经济线 K条商业线 (后面跟了一堆各种奇奇怪怪的线路)该上路了,作为一名老司机,你肯定知道走哪条路线节省时间时间就是金钱哇(#^.^#)
本题使用Dijkstra算法
关于Dijkstra算法,具体内容可以参考 Dijkstra算法代码可以背一下,然后悄悄咪咪扒出课堂上的讲解 test data4 1 441 2 21 3 32 4 43 4 512 4 3
output
1 2 4 2 5解题过程
图解:图片有点丑,凑活着看吧。先说说Dijkstra的松弛操作:Dijkstra算法算是贪心思想实现的,松弛操作就是,遍历一遍。看通过刚刚找到的最短距离的点作为中转站会不会更近,如果更近了就更新距离,这样把所有的点找遍之后就存下了起点到其他所有点的最短距离。
首先起点1终点4首先有个dis记录0 2 3 ∞看图得知1到4是无穷远的,所以肯定有中间点1 到 2最近(排除到它自身)点2 确定2 到4最近,4确定,因为终点就是4,结束
Codes
#include#include #include #include #include using namespace std;const int maxn=1e5+10;const int Inf=1e8;//本来开始设为了0x3f3f3f3f,不知道为什么会报错emmmm struct edge{ int to,next,w;};edge e[maxn];int head[maxn],vis[maxn],dis1[maxn],dis2[maxn],pre1[maxn],pre2[maxn];int ans,tot,N,S,E,M,K,a,b,c,ld,rd;//N个点,S起点,E终点,M个经济点,K个商业点 priority_queue > Q;//最大堆,解决负环的问题,其实它用了最小堆,只是可以用greater和less来调节//懒人思想:代码量能省则省(我就是那个懒人 //正确思想:算法复杂度越低越好 void add_edge(int u,int v,int w){ //链式前向星加边 e[++tot].to = v; e[tot].next = head[u]; e[tot].w=w; head[u] = tot;}void dijkstra(int st,int* dis,int* pre){ //为了2次迪杰斯特拉算法节省代码 while(Q.size()) Q.pop();//清空 memset(vis,0,sizeof(vis)); for(int i = 1;i<=N;i++) dis[i]=Inf; dis[st] = 0; Q.push(make_pair(0,st)); while(!Q.empty()){ int x = Q.top().second; Q.pop(); if(vis[x]) continue; vis[x] = 1; for(int i = head[x];i;i = e[i].next){ int y = e[i].to,z = e[i].w; if(dis[y]>dis[x]+z){ dis[y] = dis[x]+z; Q.push(make_pair(-dis[y],y)); pre[y] = x; } } }}void print1(int st,int ed){ //输出 if(pre1[ed]==0){ cout< >N>>S>>E){ if(tag!=0) cout< >M; for(int i=0;i >a>>b>>c; add_edge(a,b,c);//利用链式前向星 add_edge(b,a,c);//因为路段是双向的,题目有说 } dijkstra(S,dis1,pre1);//两次迪杰斯特拉算法 dijkstra(E,dis2,pre2); cin>>K; for(int i=1;i<=K;i++){ cin>>a>>b>>c;//商业线 if(dis1[a]+dis2[b]+c
转载地址:http://kdwzi.baihongyu.com/