AcWing 383. Sightseeing problem solution (shortest circuit)

AcWing 383. Sightseeing
It is similar to finding the shortest path , It's just another short circuit , It is necessary to consider under what circumstances it is necessary to update the secondary short circuit status , It's wonderful to use a two-dimensional array here , Worth learning

#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];  // First dimension record point , Is the second dimension record the shortest or secondary short circuit  
bool st[N][2];  // First dimension record point , Is the second dimension record the shortest or secondary short circuit  

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;  // Initialize the distance value  
	cnt[S][0] = 1;  // Number of initialization schemes  
	
	priority_queue<Ver, vector<Ver>, greater<Ver>>heap;  // Big root pile 
	heap.push({
    S, 0, 0});  // The first point into the heap 
	
	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]){
    
				// First update the status of the secondary short circuit , Directly inherit the shortest state  
				dist[j][1] = dist[j][0];
				cnt[j][1] = cnt[j][0];
				heap.push({
    j, 1, dist[j][1]});
				// Update the status of the shortest circuit  
				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]){
      // Find a new secondary short circuit  
				dist[j][1] = d + w[i];
				cnt[j][1] = ct;
				heap.push({
    j, 1, dist[j][1]});  // Remember to join the team after finding a new point state  
			}
			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;
}