L2-001 城市间紧急救援

题干：

​ 作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。

输入格式:

输入第一行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0 ~ (N−1)；M是快速道路的条数；S是出发地的城市编号；D是目的地的城市编号。

第二行给出N个正整数，其中第i个数是第i个城市的救援队的数目，数字间以空格分隔。随后的M行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。

输出格式:

第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。

输入样例:

4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2

输出样例:

2 60
0 1 3

题意：

给定无向图，每个点有权值，求

1. S点到D点的最短路的数量
2. 最短路中最大权值并输出该条最短路的路径

思路：

（1）dijkstra求最短路+数组存储路径

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 1010;
const int inf = 0x3f3f3f3f;
typedef pair<int, int>PII;
typedef long long ll;

int n, m, s, e;
int w[N][N];//邻接矩阵记录两点直接连线距离
bool st[N];
int d[N];//起始城市到该城市的最短长度
int jy[N];//该城市救援队人数
int rs[N];//这条路线上到此城市的救援队最多人数
int p[N];//记录这条线路上这座城市的前一个城市
int lx[N];//到达此城市的路线数量

void dijkstra() {
	for (int i = 1; i <= n; i++) {
		int t = -1;
		for (int j = 1; j <= n; j++)
			if (!st[j] && (t == -1 || d[t] > d[j]))
				t = j;

		st[t] = true;

		for (int j = 1; j <= n; j++) {
			if (d[j] > d[t] + w[t][j]) {//更新最短路
				d[j] = d[t] + w[t][j];
				lx[j] = lx[t];
				p[j] = t;//记录到达j点的前一个点为t
				rs[j] = rs[t] + jy[j];//到j点的救援队人数为到t点的救援队人数+j点原有人数
			} else if (d[j] == d[t] + w[t][j]) {//最短路相同时
				lx[j] += lx[t];//路线数量叠加
				if (rs[j] < rs[t] + jy[j]) {//若该线路救援队数量更多
					p[j] = t;
					rs[j] = rs[t] + jy[j];
				}

			}
		}
	}
}

int main() {
	cin >> n >> m >> s >> e;
	s++, e++;//习惯把编号从1开始计数
	memset(d, 0x3f, sizeof d);
	d[s] = 0;
	lx[s] = 1;
	memset(w, 0x3f, sizeof w);

	for (int i = 1; i <= n; i++) {
		cin >> jy[i];
		rs[i] = jy[i];
		p[i] = i;//类似并查集的初始化
	}

	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
		a++, b++;
		w[a][b] = w[b][a] = min(w[a][b], c);
	}
	/*****求最快到达的路线*****/
	dijkstra();

	cout << lx[e] << ' ' << rs[e] << endl;

	/*****存储最快到达的路径*****/
	vector<int>ve;//vector存储路径
	int now = e;//从结束城市向前寻找路径至起始城市
	while (1) {
		ve.push_back(now);
		if (p[now] == now)
			break;

		now = p[now];
	}
	reverse(ve.begin(), ve.end());//翻转
	
	/*****输出*****/
	int f = 0;
	for (auto t : ve) {//输出
		if (f)
			cout << ' ';
		f = 1;
		cout << t - 1 ;
	}
}

(2)floyd求最短路+dfs存储路径

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 1010;
typedef pair<int, int>PII;
typedef long long ll;

int n, m, s, e;
int w[N][N];//记录两点之间最短路
int d[N][N];//记录两点直接连通的路径
int cnt;//记录最短路径条数
int maxn;//最多救援队数量
int jy[N];
vector<int>ve;//当前路径
vector<int>maxv;//最长路径

void floyd() {//弗洛伊德算法求两点之间最短路
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++) {
				w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
			}
}

void dfs(int s, int rs) {//寻找路径，s为当前点，rs为当前人数
	rs += jy[s];
	if (e == s) {//递归退出条件
		if (maxn < rs) {
			maxn = max(maxn, rs);
			maxv = ve;
		}
		cnt++;

		return;
	}

	for (int i = 1; i <= n; i++) {
		if (w[s][i] != 0x3f3f3f3f && w[s][i] != 0
		        && w[s][e] == d[s][i] + w[i][e]) { //不能w[s][e] == w[s][i] + w[i][e],要保证s和i有直接路径相通
			ve.push_back(i);
			dfs(i, rs);
			ve.pop_back();
		}
	}

}

int main() {
	cin >> n >> m >> s >> e;
	s++, e++;
	for (int i = 1; i <= n; i++)//弗洛伊德初始化
		for (int j = 1; j <= n; j++) {
			if (i == j)
				d[i][j] = w[i][j] = 0;
			else
				d[i][j] = w[i][j] = 0x3f3f3f3f;
		}

	for (int i = 1; i <= n; i++)
		cin >> jy[i];
	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
		a++, b++;
		w[a][b] = w[b][a] = min(w[a][b], c);
		d[a][b] = d[b][a] = min(d[a][b], c);
	}
	floyd();
	ve.push_back(s);
	dfs(s, 0);
	cout << cnt << ' ' << maxn << endl;
	int f = 0;
	for (auto t : maxv) {
		if (f)
			cout << ' ';
		cout << t - 1;
		f = 1;
	}


}

L3-007 天梯地图

题干：

​ 本题要求你实现一个天梯赛专属在线地图，队员输入自己学校所在地和赛场地点后，该地图应该推荐两条路线：一条是最快到达路线；一条是最短距离的路线。题目保证对任意的查询请求，地图上都至少存在一条可达路线。

输入格式:

输入在第一行给出两个正整数N（2 ≤ N ≤ 500）和M，分别为地图中所有标记地点的个数和连接地点的道路条数。随后M行，每行按如下格式给出一条道路的信息：

V1 V2 one-way length time

其中V1和V2是道路的两个端点的编号（从0到N-1）；如果该道路是从V1到V2的单行线，则one-way为1，否则为0；length是道路的长度；time是通过该路所需要的时间。最后给出一对起点和终点的编号。

输出格式:

首先按下列格式输出最快到达的时间T和用节点编号表示的路线：

Time = T: 起点 => 节点1 => ... => 终点

然后在下一行按下列格式输出最短距离D和用节点编号表示的路线：

Distance = D: 起点 => 节点1 => ... => 终点

如果最快到达路线不唯一，则输出几条最快路线中最短的那条，题目保证这条路线是唯一的。而如果最短距离的路线不唯一，则输出途径节点数最少的那条，题目保证这条路线是唯一的。

如果这两条路线是完全一样的，则按下列格式输出：

Time = T; Distance = D: 起点 => 节点1 => ... => 终点

输入样例1:

10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
5 4 0 2 3
5 9 1 1 4
0 6 0 1 1
7 3 1 1 2
8 3 1 1 2
2 5 0 2 2
2 1 1 1 1
1 5 0 1 3
1 4 0 1 1
9 7 1 1 3
3 1 0 2 5
6 3 1 2 1
5 3

输出样例1:

Time = 6: 5 => 4 => 8 => 3
Distance = 3: 5 => 1 => 3

输入样例2:

7 9
0 4 1 1 1
1 6 1 3 1
2 6 1 1 1
2 5 1 2 2
3 0 0 1 1
3 1 1 3 1
3 2 1 2 1
4 5 0 2 2
6 5 1 2 1
3 5

输出样例2:

Time = 3; Distance = 4: 3 => 2 => 5

题意：

给定图，图中有有向边和无向边，每个点有权值，求

1. 起点到终点的最短路及其路径
2. 起点到终点最少耗时路及其路径

思路：

dijkstra跑两次分别求最短路和最少耗时路+数组存储路径+vector存储最终路径并判断两条线路是否相同

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 1010;
const int inf = 0x3f3f3f3f;
typedef pair<int, int>PII;
typedef long long ll;

int n, m, s, e;
int w[N][N];//邻接矩阵记录两点直接连线距离
int co[N][N];//邻接矩阵记录两点直接连线时间
bool st[N];//记录该点是否被松弛过
int d[N];//记录最短路程
int si[N];//记录该线路到达该点时经过的节点数
int ti[N];//记录最短时间
int p[N];//记录这条线路上这座城市的前一个城市

void dijkstra1() {//求时间最短
	memset(st, 0, sizeof st);
	for (int i = 1; i <= n; i++) {
		int t = -1;
		for (int j = 1; j <= n; j++) {
			if (!st[j] && (t == -1 || ti[t] > ti[j]))
				t = j;
		}
		st[t] = true;

		for (int j = 1; j <= n; j++) {
			if (ti[j] > ti[t] + co[t][j]) {//更新最短时间路
				ti[j] = ti[t] + co[t][j];
				p[j] = t;
				d[j] = d[t] + w[t][j];
			} else if (ti[j] == ti[t] + co[t][j]) {//最短时间路相同时求最短距离路
				if (d[j] > d[t] + w[t][j]) {
					p[j] = t;
					d[j] = d[t] + w[t][j];
				}

			}
		}
	}
}


void dijkstra2() {//求路程最短
	memset(st, 0, sizeof st);
	memset(d, 0x3f, sizeof d);//重置最短路
	d[s] = 0;
	fill(si, si + n + 10, 1);
	for (int i = 1; i <= n; i++) {
		int t = -1;
		for (int j = 1; j <= n; j++) {
			if (!st[j] && (t == -1 || d[t] > d[j]))
				t = j;
		}
		st[t] = true;

		for (int j = 1; j <= n; j++) {
			if (d[j] > d[t] + w[t][j]) {//更新最短距离路
				d[j] = d[t] + w[t][j];
				si[j] = si[t] + 1;
				p[j] = t;
			} else if (d[j] == d[t] + w[t][j]) {//最短距离路相同时求最少节点路
				if (si[j] > si[t] + 1) {
					p[j] = t;
					si[j] = si[t] + 1;
				}

			}
		}
	}
}

int main() {
	cin >> n >> m;

	memset(d, 0x3f, sizeof d);
	memset(ti, 0x3f, sizeof ti);
	memset(w, 0x3f, sizeof w);
	memset(co, 0x3f, sizeof co);

	while (m--) {
		int aa, bb, cc, dd, ee;
		cin >> aa >> bb >> cc >> dd >> ee;
		aa++, bb++;
		if (cc) {
			w[aa][bb] = min(w[aa][bb], dd);
			co[aa][bb] = min(co[aa][bb], ee);
		} else {
			w[aa][bb] = w[bb][aa] = min(w[aa][bb], dd);
			co[aa][bb] = co[bb][aa] = min(co[aa][bb], ee);
		}
	}
	cin >> s >> e;
	s++, e++;
	d[s] = 0;
	ti[s] = 0;

	/*****求最快到达的路线*****/
	for (int i = 1; i <= n; i++)
		p[i] = i;
	dijkstra1();
	vector<int>ve1;//vector存储路径
	int now = e;//从结束城市向前寻找路径至起始城市
	while (1) {
		ve1.push_back(now);
		if (p[now] == now) {

			break;
		}
		now = p[now];
	}
	reverse(ve1.begin(), ve1.end());//翻转

	/*****求最短距离的路线*****/
	for (int i = 1; i <= n; i++)
		p[i] = i;
	dijkstra2();
	vector<int>ve2;//vector存储路径
	now = e;//从结束城市向前寻找路径至起始城市
	while (1) {
		ve2.push_back(now);
		if (p[now] == now) {

			break;
		}
		now = p[now];
	}
	reverse(ve2.begin(), ve2.end());//翻转


	/*****输出*****/
	if (ve1 == ve2) {
		printf("Time = %d; Distance = %d: ", ti[e], d[e]);
		int f = 0;
		for (auto t : ve1) {
			if (f)
				cout << " => ";
			f = 1;
			cout << t - 1 ;
		}
	} else {
		printf("Time = %d: ", ti[e]);
		int f = 0;
		for (auto t : ve1) {
			if (f)
				cout << " => ";
			f = 1;
			cout << t - 1 ;
		}
		cout << endl;
		printf("Distance = %d: ", d[e]);
		f = 0;
		for (auto t : ve2) {
			if (f)
				cout << " => ";
			f = 1;
			cout << t - 1 ;
		}
	}
}

L3-011 直捣黄龙

题干：

​ 本题是一部战争大片 —— 你需要从己方大本营出发，一路攻城略地杀到敌方大本营。首先时间就是生命，所以你必须选择合适的路径，以最快的速度占领敌方大本营。当这样的路径不唯一时，要求选择可以沿途解放最多城镇的路径。若这样的路径也不唯一，则选择可以有效杀伤最多敌军的路径。

输入格式:

​ 输入第一行给出 2 个正整数 N（2 ≤ N ≤ 200，城镇总数）和 K（城镇间道路条数），以及己方大本营和敌方大本营的代号。随后 N-1 行，每行给出除了己方大本营外的一个城镇的代号和驻守的敌军数量，其间以空格分隔。再后面有 K 行，每行按格式城镇1 城镇2 距离给出两个城镇之间道路的长度。这里设每个城镇（包括双方大本营）的代号是由 3 个大写英文字母组成的字符串。

输出格式:

​ 按照题目要求找到最合适的进攻路径（题目保证速度最快、解放最多、杀伤最强的路径是唯一的），并在第一行按照格式己方大本营->城镇1->...->敌方大本营输出。第二行顺序输出最快进攻路径的条数、最短进攻距离、歼敌总数，其间以 1 个空格分隔，行首尾不得有多余空格。

输入样例:

10 12 PAT DBY
DBY 100
PTA 20
PDS 90
PMS 40
TAP 50
ATP 200
LNN 80
LAO 30
LON 70
PAT PTA 10
PAT PMS 10
PAT ATP 20
PAT LNN 10
LNN LAO 10
LAO LON 10
LON DBY 10
PMS TAP 10
TAP DBY 10
DBY PDS 10
PDS PTA 10
DBY ATP 10

输出样例:

PAT->PTA->PDS->DBY
3 30 210

题意：

给定无向图，每个点有权值，求

1. 起点到终点的最短路的数量
2. 起点到终点的最短路的距离
3. 最短路中经过节点最多并且权值最大的路径。

思路：

dijkstra求最短路+数组存储路径

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 1010;
const int inf = 0x3f3f3f3f;
typedef pair<int, int>PII;
typedef long long ll;

int n, m, s, e;
int a[N];//记录敌军数
int w[N][N];//邻接矩阵记录两点直接连线距离
bool st[N];//记录该点是否被松弛过
int d[N];//记录最短路程
int si[N];//记录经过节点数
int ss[N];//记录歼敌总数
int lx[N];//记录最快进攻路径条数
map<string, int>mp;//字符串映射为下标
map<int, string>mmp;//逆运算  下标映射为字符串
int idx;//字符串对应的下标
int p[N];

void dijkstra() {
	fill(si, si + n + 10, 1);
	for (int i = 1; i <= n; i++) {
		int t = -1;
		for (int j = 1; j <= n; j++) {
			if (!st[j] && (t == -1 || d[t] > d[j]))
				t = j;
		}
		st[t] = true;

		for (int j = 1; j <= n; j++) {
			if (d[j] > d[t] + w[t][j]) {//更新最短路程路
				lx[j] = lx[t];
				d[j] = d[t] + w[t][j];
				p[j] = t;
				si[j] = si[t] + 1;
				ss[j] = ss[t] + a[j];
			} else if (d[j] == d[t] + w[t][j] && (si[j] < si[t] + 1)) { //最短路程路相同的情况下找经过的节点最多
				p[j] = t;
				lx[j] += lx[t];
				si[j] = si[t] + 1;
				ss[j] = ss[t] + a[j];
			} else if (d[j] == d[t] + w[t][j] && (si[j] == si[t] + 1)
			           && (ss[j] < ss[t] + a[j])) {//最短路和经过节点都相同的情况下找杀伤敌军最多
				p[j] = t;
				lx[j] += lx[t];
				si[j] = si[t] + 1;
				ss[j] = ss[t] + a[j];
			} else if (d[j] == d[t] + w[t][j])
				lx[j] += lx[t];
		}
	}
}

int main() {
	cin >> n >> m;
	string s1, s2;
	cin >> s1 >> s2;
	mp[s1] = ++idx; //固定起始城市标号为1
	mmp[idx] = s1;
	mp[s2] = n; //固定结束城市标号为n
	mmp[n] = s2;

	memset(d, 0x3f, sizeof d);
	memset(w, 0x3f, sizeof w);
	d[1] = 0;
	lx[1] = 1;
	for (int i = 1; i < n; i++) {
		string str;
		cin >> str;
		if (!mp[str]) {
			mp[str] = ++idx;
			mmp[idx] = str;
		}
		cin >> a[mp[str]];
	}
	while (m--) {
		int c;
		cin >> s1 >> s2 >> c;
		int a = mp[s1], b = mp[s2];
		w[a][b] = w[b][a] = min(w[a][b], c);
	}

	/*****求最快到达的路线*****/
	for (int i = 1; i <= n; i++)
		p[i] = i;
	dijkstra();
	vector<int>ve1;//vector存储路径
	int now = n;//从结束城市向前寻找路径至起始城市
	while (1) {
		ve1.push_back(now);
		if (p[now] == now) {

			break;
		}
		now = p[now];
	}
	reverse(ve1.begin(), ve1.end());//翻转

	/*****输出*****/
	int f = 0;
	for (auto t : ve1) {
		if (f)
			cout << "->";
		f = 1;
		cout << mmp[t] ;
	}
	cout << endl;
	cout << lx[n] << ' ' << d[n] << ' ' << ss[n] << endl;


}

L3-022 地铁一日游

题干：

​ 森森喜欢坐地铁。这个假期，他终于来到了传说中的地铁之城——魔都，打算好好过一把坐地铁的瘾！

魔都地铁的计价规则是：起步价 2 元，出发站与到达站的最短距离（即计费距离）每 K 公里增加 1 元车费。

例如取 K = 10，动安寺站离魔都绿桥站为 40 公里，则车费为 2 + 4 = 6 元。

为了获得最大的满足感，森森决定用以下的方式坐地铁：在某一站上车（不妨设为地铁站 A），则对于所有车费相同的到达站，森森只会在计费距离最远的站或线路末端站点出站，然后用森森美图 App 在站点外拍一张认证照，再按同样的方式前往下一个站点。

坐着坐着，森森突然好奇起来：在给定出发站的情况下（在出发时森森也会拍一张照），他的整个旅程中能够留下哪些站点的认证照？

地铁是铁路运输的一种形式，指在地下运行为主的城市轨道交通系统。一般来说，地铁由若干个站点组成，并有多条不同的线路双向行驶，可类比公交车，当两条或更多条线路经过同一个站点时，可进行换乘，更换自己所乘坐的线路。举例来说，魔都 1 号线和 2 号线都经过人民广场站，则乘坐 1 号线到达人民广场时就可以换乘到 2 号线前往 2 号线的各个站点。换乘不需出站（也拍不到认证照），因此森森乘坐地铁时换乘不受限制。

输入格式:

​ 输入第一行是三个正整数 N、M 和 K，表示魔都地铁有 N 个车站 (1 ≤ N ≤ 200)，M 条线路 (1 ≤ M ≤ 1500)，最短距离每超过 K 公里 (1 ≤ K ≤ 106)，加 1 元车费。

接下来 M 行，每行由以下格式组成：

<站点1><空格><距离><空格><站点2><空格><距离><空格><站点3> … <站点X-1><空格><距离><空格><站点X>

其中站点是一个 1 到 N 的编号；两个站点编号之间的距离指两个站在该线路上的距离。两站之间距离是一个不大于 106 的正整数。一条线路上的站点互不相同。

注意：两个站之间可能有多条直接连接的线路，且距离不一定相等。

再接下来有一个正整数 Q (1 ≤ Q ≤ 200)，表示森森尝试从 Q 个站点出发。

最后有 Q 行，每行一个正整数 *Xi**，表示森森尝试从编号为 *Xi 的站点出发。

输出格式:

​ 对于森森每个尝试的站点，输出一行若干个整数，表示能够到达的站点编号。站点编号从小到大排序。

输入样例:

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

输出样例:

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

题意：

给定无向图，起步价2元每K公里多加1元，求从询问点上车能到达的所有点，并从小到大排序输出

其中能到达的点的定义：计费距离最远的站或线路末端站点出站，并从该出站点能到达的所有点

思路：

floyd求最短路后二重循环遍历统计每个点不靠转乘能到达的所有点，再用dfs搜索靠转乘能到达的所有站点

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 1010;
const int inf = 0x3f3f3f3f;
typedef pair<int, int>PII;
typedef long long ll;

int n, m, t, k, s;
int w[N][N];//两点之间最短距离
bool f[N];//标记是否为末端站点
vector<int>ve[N];//记录任一点不靠转乘能到达的点
bool st[N];//标记一个点是否能被到达

void dfs(int s) {//dfs找能靠转乘到达的点
	for (auto t : ve[s]) {
		if (!st[t]) {//如果未被遍历过
			st[t] = true;
			dfs(t);//在该点转乘，即以该点为起点继续dfs
		}
	}
}

int main() {

	cin >> n >> m >> k;

	/*****弗洛伊德算法初始化*****/
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (i == j)
				w[i][j] = 0;
			else
				w[i][j] = inf;

	/*****读入路程距离*****/
	while (m--) {
		int a, b, c;
		cin >> a;
		f[a] = true;
		while (getchar() != '\n') {
			cin >> b >> c;
			w[a][c] = w[c][a] = min(w[a][c], b);
			a = c;  //要不然就一直是起点x到各个站点的距离了
		}
		f[c] = true;

	}

	/*****弗洛伊德算任意两点最短路*****/
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				w[i][j] = min(w[i][j], w[i][k] + w[k][j]);

	/*****计算任一点不靠转乘能到达的点*****/
	for (int i = 1; i <= n; ++i) {
		map<int, int> cost;//cost[i]=j代表i块钱能到达的最远距离
		/***计算相同价格所能到达的最远的点***/
		for (int j = 1; j <= n; ++j)//
			if (w[i][j] != inf)
				cost[2 + w[i][j] / k] = max(cost[2 + w[i][j] / k], w[i][j]);
		/***统计能到达的点***/
		for (int j = 1; j <= n; ++j)
			if (cost[2 + w[i][j] / k] == w[i][j] || f[j] && w[i][j] != inf)
				ve[i].push_back(j);
	}

	/*****回答询问*****/
	cin >> m;
	while (m--) {
		cin >> s;
		memset(st, 0, sizeof st);
		dfs(s);
		st[s] = true;
		/***输出***/
		int flag = 0;
		for (int i = 1; i <= n; i++) {
			if (st[i]) {
				if (flag)
					cout << ' ';
				flag = 1;
				cout << i;
			}
		}
		cout << endl;
	}

}