題目鏈接戳這里
dijkstra模板,源點(diǎn)到點(diǎn)i,經(jīng)u有更短路,更新到i的救援隊(duì)數(shù)cjy[i]=cjy[u]+jy[i],更新到點(diǎn)i的路徑數(shù)ts[i]=ts[u]
若經(jīng)u是原先到i的同等長度的路徑,路徑之間是平等關(guān)系,和起來: ts[i] += ts[u],同理更新一下其它值,注意同等長度遇到救援隊(duì)數(shù)更多時(shí)要修改路徑.

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

#define mst(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
const int inf = 0x3f3f3f3f, maxN = 505;
int N, M, S, D;
// 城市存的救援人數(shù) 圖 是否已在集合S中的標(biāo)記
int jy[maxN], G[maxN][maxN], ins[maxN];
// 到i城路徑條數(shù) 到i城的救援人數(shù) 前一個(gè)節(jié)點(diǎn) 最短距離d
int ts[maxN], cjy[maxN], pre[maxN], d[maxN];

void dijkstra(int s) {
    mst(ins, 0);
    mst(d, inf);
    mst(cjy, 0);
    mst(pre, -1);
    mst(ts, 0);
    cjy[s] = jy[s];
    ts[s] = 1;
    d[s] = 0;

    while (1) {
        int u = -1;
        rep(i, 0, N)
            if (!ins[i] && (u == -1 || d[i] < d[u]))
                u = i;
        if (u == -1)
            break;
        ins[u] = 1;
        rep(i, 0, N) {
            if (!ins[i] && G[u][i] < inf) {
                if (d[u] + G[u][i] < d[i]) {
                    d[i] = d[u] + G[u][i];
                    pre[i] = u;
                    cjy[i] = cjy[u] + jy[i];
                    ts[i] = ts[u];
                } else if (d[u] + G[u][i] == d[i]) {
                    ts[i] += ts[u];
                    if (cjy[u] + jy[i] > cjy[i]) {
                        cjy[i] = cjy[u] + jy[i];
                        pre[i] = u;
                    }
                }
            }
        }
    }
}

void print_path(int e) {
    int rec[maxN], idx = 0;
    while (e != -1) {
        rec[idx++] = e;
        e = pre[e];
    }
    rep(i, 0, idx) {
        if (i) printf(" ");
        printf("%d", rec[idx - 1 - i]);
    }
}

int main() {
    // freopen("data.in", "r", stdin);
    scanf("%d%d%d%d", &N, &M, &S, &D);
    rep(i, 0, N) scanf("%d", &jy[i]);

    int from, to, dis;
    mst(G, inf);
    rep(i, 0, M) {
        scanf("%d %d %d", &from, &to, &dis);
        G[from][to] = G[to][from] = dis;
    }
    dijkstra(S);
    printf("%d %d\n", ts[D], cjy[D]);
    print_path(D);

    return 0;
}