好久没有写记录信息的最短路了

题目描述见链接 https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=994805073643683840&page=1

用dijkstr查找最短路，在更新最短路的同时更新最短路径数量cnt，救援队数量sum，最佳路径起点pre。
数据没有给边的范围，所以先用矩阵保存，然后再转成链式前向星。注意边的大小要开到250010

代码如下：

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#define x first
#define y second
using namespace std;

typedef pair<int,int> PII;
const int N = 510,M = 250010;
int w[N];
int n,m,s,d;
int head[N],ne[M],to[M],e[M],idx;
int dist[N];//记录距离
int cnt[N], sum[N], pre[N]; //分别表示记录路径数量，救援队数量，最佳路径起点，
bool st[N];
int map[N][N]; //保存图信息

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

void dijkstr()
{
    memset(dist,0x3f,sizeof dist);
    dist[s] = 0, cnt[s] = 1, sum[s] = w[s], pre[s] = -1;
    priority_queue<PII,vector<PII>,greater<PII>> q;
    q.push({0,s});

    while(q.size()){
        auto t = q.top();q.pop();
        int ver = t.y;

        if(st[ver]) continue;
        st[ver] = true;
        for(int i = head[ver];i!=-1;i = ne[i]) {
            int j = to[i];
            if(dist[j] > dist[ver] + e[i]) { //最短路被替换
                dist[j] = dist[ver] + e[i];
                cnt[j] = cnt[ver]; //最短路的条数
                sum[j] = sum[ver] + w[j]; //最短路节点上的值的总和
                pre[j] = ver; //上一节点
                q.push({dist[j],j});
            }
            else if(dist[j] == dist[ver] + e[i]) { //有同样的最短路
                cnt[j] += cnt[ver];
                if(sum[ver] + w[j] > sum[j]) {
                    sum[j] = sum[ver] + w[j];
                    pre[j] = ver;
                }
            }
        }
    }
}

int main()
{
    memset(head,-1,sizeof head);
    memset(map,0x3f,sizeof map);
    cin>>n>>m>>s>>d;
    for(int i = 0;i<n;i++) cin>>w[i];
    for(int i = 0;i<m;i++) {
        int a,b,c;
        cin>>a>>b>>c;
        map[a][b] = min(map[a][b],c);
        map[b][a] = min(map[a][b],c);
//      add(a,b,c);
//      add(b,a,c);
    }
    for(int i = 0;i<n;i++) 
        for(int j = 0;j<n;j++) {
            if(map[i][j] < N) add(i,j,map[i][j]);
        }
    dijkstr();
    vector<int> ans;
    for(int i = pre[d];i!=s;i = pre[i]) ans.push_back(i);
    reverse(ans.begin(),ans.end());
    cout<<cnt[d]<<' '<<sum[d]<<endl;
    cout<<s<<' ';
    for(auto it : ans) cout<<it<<' ';
    cout<<d;
    return 0;
}