383. 观光(dp思想运用，Dijkstra)

383. 观光 - AcWing题库

“您的个人假期”旅行社组织了一次比荷卢经济联盟的巴士之旅。

比荷卢经济联盟有很多公交线路。

每天公共汽车都会从一座城市开往另一座城市。

沿途汽车可能会在一些城市（零或更多）停靠。

旅行社计划旅途从?S?城市出发，到?F?城市结束。

由于不同旅客的景点偏好不同，所以为了迎合更多旅客，旅行社将为客户提供多种不同线路。

游客可以选择的行进路线有所限制，要么满足所选路线总路程为?S?到?F?的最小路程，要么满足所选路线总路程仅比最小路程多一个单位长度。

如上图所示，如果?S=1，F=5，则这里有两条最短路线?1→2→5,1→3→5，长度为?6；有一条比最短路程多一个单位长度的路线?1→3→4→5，长度为?7。

现在给定比荷卢经济联盟的公交路线图以及两个城市?S?和?F，请你求出旅行社最多可以为旅客提供多少种不同的满足限制条件的线路。

输入格式

第一行包含整数?T，表示共有?T?组测试数据。

每组数据第一行包含两个整数?N?和?M，分别表示总城市数量和道路数量。

接下来?M?行，每行包含三个整数?A,B,L，表示有一条线路从城市?A?通往城市?B，长度为?L。

需注意，线路是?单向的，存在从?A?到?B?的线路不代表一定存在从?B?到?A?的线路，另外从城市?A?到城市?B 可能存在多个不同的线路。

接下来一行，包含两个整数?S?和?F，数据保证?S?和?F?不同，并且?S、F?之间至少存在一条线路。

输出格式

每组数据输出一个结果，每个结果占一行。

数据保证结果不超过?109。

数据范围

2≤N≤1000,
1≤M≤10000,
1≤L≤1000，
1≤A,B,S,F≤N

输入样例：

2
5 8
1 2 3
1 3 2
1 4 5
2 3 1
2 5 3
3 4 2
3 5 4
4 5 3
1 5
5 6
2 3 1
3 2 1
3 1 10
4 5 2
5 2 7
5 2 7
4 1

输出样例：

3
2

解析：

最短路径的条数。

如果存在比最短路径长度恰好多1的路径，则再把这样的路径条数加上。

状态划分：不重不漏，将状态转移所依据的状态体现出来；

d[i,0]表示从1到i的最短路径距离，cnt[i,0]最短路径条数

d[i,1]表示从1到i的次短路径距离，cnt[i,1]次短路径条数

这里还是和之前的题目一样，将d[i,0]和d[i,1]两种状态看成两个点。

重点解决：d[i,1]表示从1到i的次短路径，具体看代码处理。

本题很好，非常值得回味！

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
const int N = 1e3 + 5, M = 1e4 + 5;
struct Ver {
	int ver, type, dist;
	bool operator > (const Ver& W) const {
		return dist > W.dist;
	}
};
int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx;
int dist[N][2], cnt[N][2];
int vis[N][2];

void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int Dijkstra() {
	memset(dist, 0x3f, sizeof dist);
	memset(cnt, 0, sizeof cnt);
	priority_queue<Ver, vector<Ver>, greater<Ver>>heap;
	dist[S][0] = 0, cnt[S][0] = 1;
	heap.push({ S,0,0 });
	while (!heap.empty()) {
		Ver t = heap.top();
		heap.pop();
		int ver = t.ver, type = t.type, d = t.dist, count = cnt[ver][type];
		if (vis[ver][type])continue;
		vis[ver][type] = 1;

		//cout << "__________________________________" << ver << endl;

		for (int i = h[ver]; i != -1; i = ne[i]) {
			int j = e[i];
			
			//cout << "++++++++++++++++++" << j << endl;

			if (dist[j][0] > d + w[i]) {
				dist[j][1] = dist[j][0];
				cnt[j][1] = cnt[j][0];
				heap.push({ j,1,dist[j][1] });
				dist[j][0] = d + w[i];
				cnt[j][0] = count;
				heap.push({ j,0,dist[j][0] });
			}
			else if (dist[j][0] == d + w[i]) {
				cnt[j][0] += count;
			}
			else if (dist[j][1] > d + w[i]) {
				dist[j][1] = d + w[i];
				cnt[j][1] = count;
				heap.push({ j,1,dist[j][1] });
			}
			else if(dist[j][1] == d + w[i]) {
				cnt[j][1] += count;
			}
		}
	}
	int ret = cnt[T][0];
	if (dist[T][1] == dist[T][0] + 1)ret += cnt[T][1];
	return ret;
}

int main() {
	int TT;
	cin >> TT;
	while (TT--) {
		memset(h, -1, sizeof h);
		memset(vis, 0, sizeof vis);
		idx = 0;
		scanf("%d%d", &n, &m);
		for (int i = 1, a, b, c; i <= m; i++) {
			scanf("%d%d%d", &a, &b,&c);
			add(a, b, c);
		}
		scanf("%d%d", &S, &T);
		printf("%d\n", Dijkstra());
		/*cout << endl << endl;
		for (int i = 1; i <= n; i++) {
			cout << dist[i][0] << " ";
		}
		cout << endl;
		for (int i = 1; i <= n; i++) {
			cout << cnt[i][0] << " ";
		}
		cout << endl<<endl;
		for (int i = 1; i <= n; i++) {
			cout << dist[i][1] << " ";
		}
		cout << endl;
		for (int i = 1; i <= n; i++) {
			cout << cnt[i][1] << " ";
		}
		cout << endl;*/
	}
	return 0;
}