c++代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>

using namespace std;

const int N = 510;
int n, m, s, d;
int g[N][N], w[N];
bool st[N];
int dist[N], p[N];
//数组num[i]存的是从起点到结点i最短路径的条数
//数组f[i]存的是最短路径中，从起点到结点i可召集的救援队数量的最大值
int num[N], f[N];

void dijkstra(int u) {
    memset(dist, 0x3f, sizeof dist);
    dist[u] = 0;
    memset(p, -1, sizeof p);
    num[s] = 1;
    f[s] = w[s];

    for (int i = 0; i < n; i++) {
        int t = -1;

        for (int i = 0; i < n; i++)
            if (!st[i] && (t == -1 || dist[t] > dist[i]))
                t = i;

        st[t] = true;

        for (int i = 0; i < n; i++) 
            //起点到结点i的最短路径只有一条时
            if (dist[i] > dist[t] + g[t][i]) {
                dist[i] = dist[t] + g[t][i];
                num[i] = num[t];
                p[i] = t;
                f[i] = f[t] + w[i];
            }//从起点到结点i的最短路径不止一条时
            else if (dist[i] == dist[t] + g[t][i]) {
                num[i] += num[t];
                if (f[t] > f[i] - w[i]) {
                    p[i] = t;
                    f[i] = f[t] + w[i];
                }
            }


    }
}

int main() {
    cin >> n >> m >> s >> d;

    for (int i = 0; i < n; i++) cin >> w[i];

    memset(g, 0x3f, sizeof g);
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = c;
    }

    dijkstra(s);

    cout << num[d] << " " << f[d] << endl;

    stack<int> cnt;
    for (int i = p[d]; ~i; i = p[i]) cnt.push(i);

    while (!cnt.empty()) {
        cout << cnt.top() << " ";
        cnt.pop();
    }
    cout << d;

    return 0;
}