L2-001 emergency rescue (extension of shortest Dijkstra - number of shortest paths & maximum weight of paths)

Ideas ： Vegetables only seek the shortest path , Will not expand /(ㄒoㄒ)/~~. Reference blog

Code implementation ： 

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 510;

int n, m, s, d;
int ans, u, v, w;
int g[N][N], c[N]; // Adjacency matrix edge storage , c[i] It means the first one i Number of rescue teams in cities 
int dis[N], path[N]; //dis[i] Express s->i Shortest path ,   path[i] Transfer to i Last status node of 
int num[N], p[N], mx[N]; //num[i] Express s->i Number of shortest paths , p[i] Store the cities you pass , mx[i] Express s->i Maximum number of rescues 
bool vis[N];

void dijkstra()
{
    for(int i = 0; i < n; i ++){
        int t = -1;
        for(int j = 0; j < n; j ++){ // First find the nearest point that is not used as an intermediate node 
            if(!vis[j]&&(t==-1||dis[t]>dis[j])){
                t = j;
            }
        }
        vis[t] = 1; // Mark it as used 
        for(int j = 0; j < n; j ++){ // Use this intermediate node to handle other points 

            if(dis[t]+g[t][j]<=dis[j]){ // Update if the path is shorter 

                if(dis[t]+g[t][j]==dis[j]){ // situation 1： When the path length is the same ,dis The value is not updated 
                    num[j] += num[t];  // Increased number of paths 
                    if(mx[t]+c[j]>mx[j]){
                        mx[j] = mx[t]+c[j]; // Update the maximum number of rescues 
                        path[j] = t;
                    }
                }
                else{ // The path length is smaller , Then all values are forced to update 
                    num[j] = num[t];
                    mx[j] = mx[t]+c[j];
                    path[j] = t;
                    dis[j] = dis[t]+g[t][j];
                }
            }
        }
    }
    int last = d; // Start at the end and go back to the starting point 
    while(last!=s){
        p[ans++] = last; // Record an answer every time you pass through a city ans
        last = path[last]; // Update the current end value 
    }
    p[ans++] = last; // The starting point also needs to be included in the passing city 
    cout << num[d] << " " << mx[d] << endl;
    for(int i = ans-1; ~i; i --){ // Just export all the cities you pass 
        cout << p[i] << " \n"[!i];
    }
}


signed main()
{
    cin >> n >> m >> s >> d;
    memset(g, 0x3f, sizeof(g));
    memset(dis, 0x3f, sizeof(dis));
    for(int i = 0; i < n; i ++){
        cin >> c[i];
        mx[i] = c[i];
    }
    for(int i = 0; i < m; i ++){
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = w;
    }
    num[s] = 1;
    dis[s] = 0;
    dijkstra();

    return 0;
}