AcWing 383. 观光 题解（最短路）

AcWing 383. 观光
和找最短路方案类似，只不过多了一次次短路，需要考虑在什么情况下需要更新次短路状态，这里用二维数组表示很妙，值得学习

#include<bits/stdc++.h>

using namespace std;

const int N = 1010, M = 20010;

int cse;
int h[N], e[M], w[M], ne[M], idx;
int S, T, n, m;
int dist[N][2], cnt[N][2];  //第一维记录点，第二维记录是最短路还是次短路 
bool st[N][2];  //第一维记录点，第二维记录是最短路还是次短路 

struct Ver{
	int id, type, dist;
	bool operator> (const Ver &W) const{
		return dist > W.dist;
	}
};

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

int dijkstra(){
	memset(st, 0, sizeof st);
	memset(cnt, 0, sizeof cnt);
	memset(dist, 0x3f, sizeof dist);
	
	dist[S][0] = 0;  //初始化距离值 
	cnt[S][0] = 1;  //初始化方案数 
	
	priority_queue<Ver, vector<Ver>, greater<Ver>>heap;  //大根堆
	heap.push({S, 0, 0});  //第一个点入堆
	
	while(heap.size()){
		Ver v = heap.top();
		heap.pop();
		
		int ver = v.id, type = v.type, d = v.dist, ct = cnt[ver][type];
		
		if(st[ver][type]) continue;
		st[ver][type] = true;
		
		for(int i = h[ver]; ~i; i = ne[i]){
			int j = e[i];
			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] = ct;
				heap.push({j, 0, dist[j][0]});
			}
			else if(dist[j][0] == d + w[i]){
				cnt[j][0] += ct;
			}
			else if(dist[j][1] > d + w[i]){  //找到新的次短路 
				dist[j][1] = d + w[i];
				cnt[j][1] = ct;
				heap.push({j, 1, dist[j][1]});  //找到新的点状态之后记得入队 
			}
			else if(dist[j][1] == d + w[i]){
				cnt[j][1] += ct; 
			}
		}
	} 
	
	int res = cnt[T][0];
	if(dist[T][0] + 1 == dist[T][1]) res += cnt[T][1];
	
	return res;
}

int main()
{
	cin>>cse;
	while(cse -- ){
		cin>>n>>m;
		memset(h, -1, sizeof h);
		idx = 0; 
		while(m -- ){
			int a, b, c;
			cin>>a>>b>>c;
			add(a, b, c);
		}
		cin>>S>>T;
		cout<<dijkstra()<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95