快线换乘-最短路径

最短路径

问题描述

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

Input

输入包含多组数据。每组数据第一行为 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 行是商业线路段的描述，格式同经济线。

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

Output

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

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

Sample

Input: 
4 1 4
4
1 2 2
1 3 3
2 4 4
3 4 5
1
2 4 3

Output: 
1 2 4
2
5

Limitation

Time limit		1000 ms

解题思路

不考虑商业线，这是一个没有负边的单源最短路问题，用Dijksta算法求解即可。

Dijkstra Algorithm

引进两个集合S和U，S记录已求出的最短路径的顶点，U记录还未求出最短路径的顶点。

从一个起点s出发，初始时，S中只有s，U中有除s外的其它顶点且其距离为s到之的距离，不断的从U中选出距离最短的顶点k，并将k加入到S中，且从U中移除k。

然后更新U，(s, v)表示s到v的距离，若(s, v) > (s, k) + (k, v)，则更新(s, v)。

不断重复以上操作，直至遍历完所有顶点。

再看这道题

先不考虑商业线，从起点开始遍历，可以求出起点到每个点的最短距离dis1[]，再从终点开始遍历得到最短距离dis2[]。

考虑商业线，对于每一次输入的商业线(u, v, w)，对比一下dis1[u]+dis2[v]+w(由起点到u、由终点到v，且算上这条商业线的w)与dis1[v]+dis2[u]+w(起点→v、终点→u、商业线权重w)，取最小值，并用一个ans记录每一个的最小值，次次取最小，枚举完后记录的那个就是所取的商业线。ans再与不走商业线对比，最小值就是最终答案，根据题目格式输出。

源代码

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

struct edge{
	int to, w;
	edge* next;
	edge() { to = -1; w = -1; next = NULL; }
	edge(int _t, int _w) :to(_t), w(_w) { next = NULL; }
};

const int maxN = 505;
const int inf = 1e5;

class linkedList {
private:
	edge* head;
	int size;
public:
	linkedList() { head = NULL; size = 0; }
	~linkedList() {
		edge* temp = head;
		while (temp != NULL) {
			edge* p = temp;
			temp = temp->next;
			p = NULL;
			delete p;
		}
		delete temp;
		head = NULL;
		size = 0;
	}
	edge* getFirst() { return head; }
	void add(int to, int w) {
		edge* node = new edge(to, w);
		if (head == NULL) {
			head = node;
			return;
		}
		edge* p = head;
		edge* pp = NULL;
		while (p != NULL) {
			pp = p;
			p = p->next;
		}
		
		pp->next = node;
		size++;
	}
};

int dis1[maxN], dis2[maxN];

/*邻接链表表示的图*/
class graph {
private:
	linkedList arr[maxN];
	int size;
	int pre1[maxN];
	int pre2[maxN];
public:
	graph() { size = 0; }
	graph(int n) :size(n) {  }
	~graph() {  }
	void add(int x, int y, int z) {
		arr[x].add(y, z);
		arr[y].add(x, z);
	}
	void dijkstra(int s, bool sta) {
		priority_queue<pair<int, int>> q;

		bool reach[maxN] = { false };
		for (int i = 1; i <= size; i++) {
			if (sta) //判断是否是初始车站
				dis1[i] = inf;
			if (!sta)
				dis2[i] = inf;
		}
			
		if (sta)
			dis1[s] = 0;
		if (!sta)
			dis2[s] = 0;

		q.push(make_pair(0, s));

		while (!q.empty()) {
			int x = q.top().second;
			q.pop();
			if (reach[x])
				continue;
			reach[x] = true;
			for (edge* temp = arr[x].getFirst(); temp != NULL; temp = temp->next) {//遍历以当前点所有可能到达的最近车站，更新距离并记录前一车站以便输出
				int dest = temp->to;
				int weight = temp->w;
				if (sta) {
					if (dis1[dest] > dis1[x] + weight) {
						dis1[dest] = dis1[x] + weight;
						pre1[dest] = x;
						q.push(make_pair(-dis1[dest], dest));
					}
				}
				if (!sta) {
					if (dis2[dest] > dis2[x] + weight) {
						dis2[dest] = dis2[x] + weight;
						pre2[dest] = x;
						q.push(make_pair(-dis2[dest], dest));
					}
				}
				
			}
		}
	}
	void output1(int s, int cur) {
		if (s != cur)
			output1(s, pre1[cur]);
		if (s == cur)
			printf("%d", cur);
		else
			printf(" %d", cur);
	}
	void output2(int e, int cur) {
		while (cur != e) {
			printf(" %d", cur);
			cur = pre2[cur];
		}
		printf(" %d", cur);
	}
};

int main() {
	int n, s, e;//车站总数 起点 终点
	bool firstOutput = true;
	while (scanf("%d %d %d", &n, &s, &e) != EOF) {
		if (!firstOutput)
			printf("\n");

		int m;
		scanf("%d", &m);
		graph G(n);
		for (int i = 0; i < m; i++) {
			int x, y, z;
			scanf("%d %d %d", &x, &y, &z);
			G.add(x, y, z);
		}
		G.dijkstra(s, true);
		G.dijkstra(e, false);
		int k;
		scanf("%d", &k);
		int ans = inf;
		int d1, d2;
		for (int i = 0; i < k; i++) {//枚举每一条商业线
			int x, y, z;
			scanf("%d %d %d", &x, &y, &z);
			if (ans > min(dis1[x] + dis2[y] + z, dis2[x] + dis1[y] + z)) {
				ans = min(dis1[x] + dis2[y] + z, dis2[x] + dis1[y] + z);
				if (dis1[x] + dis2[y] > dis1[y] + dis2[x])
					swap(x, y);//最终变成由s到x，y到e，便于输出
				d2 = x;
				d1 = y;
			}
		}

		if (firstOutput)
			firstOutput = false;

		if (ans < dis1[e]) {//使用了车票
			G.output1(s, d2);
			G.output2(e, d1);//逆序输出
			printf("\n%d\n", d2);
		}
		else {//没使用车票 直接输出
			ans = dis1[e];
			G.output1(s, e);
			printf("\nTicket Not Used\n");
		}
		printf("%d\n", ans);
	}
	return 0;
}