Dijkstra算法

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;

const int N = 2000;
typedef pair<int,int> PII;

int e[N],ne[N],h[N],w[N],idx;
int d[N];
bool st[N];
int cnt[N],ans[N],sum[N];//cnt记录条数和 ans点权和  sum每个点的点权
int n,m,s,t;

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

void dij()
{
    memset(d,0x3f,sizeof d);
    d[s] = 0,cnt[s] = 1,ans[s] = sum[s];

    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,s});

    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second,dd = t.first;

        if(st[ver]) continue;
        st[ver] = 1;

        for(int i = h[ver]; i!=-1; i = ne[i])
        {
            int j = e[i];
            if(d[j] > dd + w[i])
            {
                d[j] = dd + w[i];
                heap.push({d[j],j});
                //最短路条数，等于上个点的条数
                cnt[j] = cnt[ver];
                //当前点点+前面点权之和
                ans[j] = ans[ver] + sum[j];
            }
            else if(d[j]==dd+w[i])
            {
                //最短条数等于当前条数加上上个点的条数
                cnt[j] += cnt[ver];
                //当前点权，与当前点权+前面点权之和，取最大值
                ans[j]=max(ans[j],ans[ver]+sum[j]);
            }
        }
    }
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m>>s>>t;
    for(int i = 0; i<n; i++) cin>>sum[i];

    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);//双向
    }
    dij();
    cout<<cnt[t]<<" "<<ans[t];
}