L2-001 emergency rescue (25 points)

The question ：

You are required to calculate the number of shortest paths and the number of rescue teams , And ask for S To D The path to success （ This path is the path with the shortest path and the largest number of rescue teams ） Plant the cities you pass ？

analysis ：

Obvious , This question uses dijkstra Algorithm , If you don't know the algorithm, you can learn it , The difficulty here is how to find the number of shortest paths and the cities , We can use three arrays to store the number of shortest paths , The number of rescue teams called , Precursor of this point , Then update these arrays when updating other points , See code for details .

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <unordered_map>
#define LL long long
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define reps(i, a, b) for(int i = a; i < b; i++) 
#define pre(i, a, b) for(int i = b; i >= a; i--)
using namespace std;

const int N = 510;

int n, m, s, d;
int g[N][N];
bool st[N];
int cnt[N], number[N]; //  It is used to store the number of rescue teams and the number of shortest paths 
int path[N]; //  Record the precursor of a point 
int dist[N], w[N];

void dijkstra()
{
    
	memset(dist, 0x3f, sizeof dist);
	dist[s] = 0;
	cnt[s] = w[s]; // Number of rescue teams at the starting point 
	number[s] = 1; // At first, the shortest path is 1
	
// cout << dist[s] << ' ' << cnt[s] << ' ' << number[s] << endl;
	rep(i, 1, n)
	{
    
		int t = -1;
		rep(j, 0, n - 1)
			if(!st[j] && (t == -1 || dist[t] > dist[j]))
				t = j;
		st[t] = true;
		
		rep(j, 0, n - 1)
		{
    
			if(dist[j] > dist[t] + g[t][j])
			{
    
				dist[j] = dist[t] + g[t][j]; // Update shortest path 
				cnt[j] = cnt[t] + w[j]; // Update the number of rescue teams 
				path[j] = t; // Record the precursor 
				number[j] = number[t]; // Update the number of shortest paths , Because it can only be seen from  t->j, That is, the number of shortest paths does not change 
			}
			
			else if(dist[j] == dist[t] + g[t][j])
			{
    
				if(cnt[j] < cnt[t] + w[j]) //  Consider the case of equal paths , Number of rescue teams 
				{
    
					cnt[j] = cnt[t] + w[j];
					path[j] = t;
				}
				
				number[j] += number[t]; // the reason being that t->j, add t The number of shortest paths is j The number of shortest paths for 
			}
		}
	}
}

int main()
{
    
	cin >> n >> m >> s >> d;
	rep(i, 0, n - 1) cin >> w[i];
	
	rep(i, 0, n - 1) path[i] = i;
	memset(g, 0x3f, sizeof g);
	
	rep(i, 1, m)
	{
    
		int x, y, z;
		cin >> x >> y >> z;
		g[x][y] = z;
		g[y][x] = z;
	}
	
	dijkstra();
	
	cout << number[d] << ' ' << cnt[d] << "\n";
	
	vector<int> ans;
	int p = d;
	while(1) // Backward path 
	{
    
		if(p == path[p])
		{
    
			ans.push_back(p);
			break;
		}
		
		ans.push_back(p);
		p = path[p];
	}
	
	pre(i, 0, ans.size() - 1) // Output in reverse order 
	{
    
		if(i != 0) cout << ans[i] << ' ';
		else cout << ans[i] << "\n";
	}
	
	return 0;
}