算法1

和最短路计数那题思路类似，只不过把宽搜换成dijkstra

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define x first
#define y second
typedef pair<int, pair<int, int>> PIII;

const int N = 510;
const int M = 610;
int n, m, c1, c2;

int e[M * 2], ne[M * 2], h[N], w[M * 2], idx;
priority_queue<PIII, vector<PIII>, greater<PIII>> pq;
int dist[N];
int st[N];
int cnt[N];
int mem[N];
int mmem[N];

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[c1] = 0;
    cnt[c1] = 1;
    pq.push({0, {c1, c1}});
    while(pq.size())
    {
        PIII t = pq.top();
        pq.pop();
        int d = t.x, p = t.y.x, pre = t.y.y;
        if(st[p])
        {
            if(d == dist[p])
            {
                cnt[p] += cnt[pre];
                mmem[p] = max(mmem[p], mmem[pre] + mem[p]);
            }
            continue;
        }
        st[p] = true;
        dist[p] = d;
        cnt[p] = cnt[pre];
        mmem[p] = mmem[pre] + mem[p];
        for(int i = h[p]; ~i; i = ne[i])
        {
            int j = e[i];
            if(!st[j])
                pq.push({dist[p] + w[i], {j, p}});
        }
    }
}

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

int main()
{
    cin >> n >> m >> c1 >> c2;
    for(int i = 0; i < n; ++ i)
        cin >> mem[i];
    memset(h, -1, sizeof h);
    int a, b, c;
    for(int i = 0; i < m; ++ i)
    {
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    dijkstra();
    printf("%d %d", cnt[c2], mmem[c2]);

}