B-TT的旅行日记 （Dijkstra算法）

一、题目描述

众所周知，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
2
5
           

二、思路与算法

本题核心算法为Dijkstra算法：

设s为源点，dis数组存储s到各点的最短距离。

初始化dis数组各值为inf（无限大），dis[s]=0，并将s加入最小堆。

这里最小堆用优先级队列实现，优先级就由到s点的距离确定。

每次从堆中取出一个点，遍历其所有邻接边（x，y，z），比较dis[y]和dis[x]+w大小关系，仍然是从直接到达、经过中间点到达两种方式中选最短的一条，每次是从目前最短的路线和正在遍历的这条路线，两者中选出最短的一条。

若dis[y]>dis[x]+w，说明经过x中转的路径比目前最短路线更短，所以替换掉dis[y]。（这就是松弛操作）

不断循环执行上述操作，直到小根堆为空。

此外，算法中用到的vis数组是记录某个元素是否已经入过队列了，因为图中都是正边，所以每个元素只入一次队列，也只被弹出一次。

三、代码实现

#include<bits/stdc++.h>
const int N=5*1e6+100;
const int M=5*1e6+100;
const int inf=5*1e8;
using namespace std;

struct Edge{
	int to,next,w;
}e[M];
int head[N],tot,n,m,vis[N],dis1[N],dis2[N];
int distant1[M],distant2[M];
int S,E,X,Y,Z,K;
int ans=inf;

void init(int* aa,int nn){
	for(int i=0;i<nn;i++){
		aa[i]=0;
	}
}

void add(int x,int y,int w){
	e[++tot].to=y;
	e[tot].next=head[x];
	e[tot].w=w;
	head[x]=tot;
} 

priority_queue< pair<int,int> >q;
void dijkstra1(int s){
	while(q.size()) q.pop();
	memset(vis,0,sizeof vis);//vis初始化 
	for(int i=1;i<=n;i++) dis1[i]=inf;//dis1初始化 
	dis1[s]=0;
	q.push(make_pair(0,s));
	while(q.size()){
		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,w=e[i].w;
			if(dis1[y]>dis1[x]+w){
				dis1[y]=dis1[x]+w;
				q.push(make_pair(-dis1[y],y));
				distant1[e[i].to]=x;
			}
		}
	}
}

void dijkstra2(int s){
	while(q.size()) q.pop();
	memset(vis,0,sizeof vis);
	for(int i=1;i<=n;i++) dis2[i]=inf;
	dis2[s]=0;
	q.push(make_pair(0,s));
	while(q.size()){
		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,w=e[i].w;
			if(dis2[y]>dis2[x]+w){
				dis2[y]=dis2[x]+w;
				q.push(make_pair(-dis2[y],y));
				distant2[e[i].to]=x;
			}
		}
	}
}

void print(int start,int end){
	if(distant1[end]==0){printf("%d",end);	return;}//起点终点重合 
	if(distant1[end]==start){printf("%d %d",start,end);	return;}
	//起点终点相连 注意一定要有！！不然无限递归下去了！ 
	else{
		print(start,distant1[end]);
		printf(" %d",end);
	}
}

void print2(int end,int start){//倒序输出 
	int ss=start;
	while(ss!=0&&ss!=end){
		printf("%d ",ss);
		ss=distant2[ss];
	}
	printf("%d",ss);
}

int main(){
	int flag=0;
	while(scanf("%d %d %d",&n,&S,&E)!=EOF){
		if(flag!=0){printf("\n");}
		scanf("%d",&m);
		for(int i=0;i<m;i++){//经济线 
			scanf("%d %d %d",&X,&Y,&Z);
			add(X,Y,Z);
			add(Y,X,Z);
		}
		dijkstra1(S);
		dijkstra2(E);
		int ld=0,rd=0;
		scanf("%d",&K);
		for(int i=0;i<K;i++){//商业线 
			scanf("%d %d %d",&X,&Y,&Z);
			if(dis1[X]+dis2[Y]+Z<ans) {
				ans=dis1[X]+dis2[Y]+Z;
				ld=X;	rd=Y;
			}
			if(dis1[Y]+dis2[X]+Z<ans){
				ans=dis1[Y]+dis2[X]+Z;
				ld=Y;	rd=X;
			}
		}//求最短路径
		//输出 
		if(dis1[E]<ans){//不走商业线 
			print(S,E);
			printf("\nTicket Not Used\n");
			printf("%d\n",dis1[E]);
		}
		else{
			print(S,ld);
			printf(" ");
			print2(E,rd);
			printf("\n%d\n",ld);
			printf("%d\n",ans);
		}
		//恢复初始化，等待下一组数据
		ans=inf;	tot=0;	flag++;
		init(head,N);	init(distant1,M);	init(distant2,M);
		 
	}
	return 0;
}
           

四、经验与总结

1. 注意，这是无向图，添加边时应该两个方向都添加一次。
2. 多组数据输入时，一定要注意每次的初始化！恢复初始态，才能开始下一组数据的处理。

3. 新接触了priority_queue结构，相关内容总结如下：

   （1）首先需要包含头文件< queue >

   （2）优先级队列就是一个用堆实现的，有优先级关系的队列，声明格式如下：

• 升序

  priority_queue <int,vector,greater > q;

• 降序

  priority_queue <int,vector,less >q;

  greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

  （3）基本操作和队列一样：

• top 访问队头元素

  empty 队列是否为空

  size 返回队列内元素个数

  push 插入元素到队尾 (并排序)

  emplace 原地构造一个元素并插入队列

  pop 弹出队头元素

  swap 交换内容

  （参考c++优先队列(priority_queue)用法详解）

1. 新接触的函数make_pair（参考关于C++ pair 和make_pair的用法）

   作用：无需写出型别， 就可以生成一个pair对象

   eg.std::make_pair(42, ‘@’);而不必费力写成std::pair<int, char>(42, ‘@’)