L2-001紧急救援_最短路径

PTA | 程序设计类实验辅助教学平台千名教师建设，万道高质量题目，百万用户拼题的程序设计实验辅助教学平台https://pintia.cn/problem-sets/994805046380707840/problems/994805073643683840

#include <bits/stdc++.h>
#define x first
#define y second
#define INF 0x3f3f3f
using namespace std;
typedef long long ll;
const int N = 512;
int n, m, s, d;
int num[N] = { 0 }, vis[N] = { 0 };
int cnt[N] = { 0 }, pre[N] = { 0 };
int g[N][N] = { 0 }, have[N] = { 0 };
int main() {
    // system("chcp 65001");
    // freopen("C:/Users/zhaochen/Desktop/input.txt", "r", stdin);
    cin.tie(0);
    cout.tie(0);
    memset(g, INF, sizeof(g));
    cin >> n >> m >> s >> d;
    for (int i = 0; i < n; i++) {
        cin >> num[i];
        cnt[i] = 1;
    }
    for (int i = 0; i < n; i++) {
        if (i != s) {
            have[i] = num[s] + num[i]; // have[i]存从s到i能得到的人数
        }
    }
    for (int i = 0; i < m; i++) {
        int a, b, len;
        cin >> a >> b >> len;
        g[a][b] = g[b][a] = len;
    }
    vis[s] = 1;
    for (int i = 1; i < n; i++) { // 在还未访问过的点中找最近的一个
        int minDis = INF, flag = 0;
        for (int j = 0; j < n; j++) {
            if (!vis[j] && g[s][j] < minDis) {
                minDis = g[s][j];
                flag = j;
            }
        }
        vis[flag] = 1;
        for (int j = 0; j < n; j++) {
            if (!vis[j]) {
                if (g[s][flag] + g[flag][j] < g[s][j]) {
                    cnt[j] = cnt[flag]; // 从s到j的最短路径的条数
                    g[s][j] = g[s][flag] + g[flag][j];
                    have[j] = have[flag] + num[j];
                    pre[j] = flag;
                } else if (g[s][flag] + g[flag][j] == g[s][j]) {
                    cnt[j] += cnt[flag];
                    if (have[j] < have[flag] + num[j]) {
                        have[j] = have[flag] + num[j];
                        pre[j] = flag;
                    }
                }
            }
        }
    }
    cout << cnt[d] << " " << have[d] << endl;
    int t = d;
    vector<int>road;
    while (t != s) {
        road.push_back(pre[t]);
        t = pre[t];
    }
    for (int i = road.size() - 1; i >= 0; i--) {
        cout << road[i] << " ";
    }
    cout << d;
    return 0;
}