题目链接
//一个没过
稠密图+朴素dijkstra

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int>PII;
const int N = 510;

int g[N][N];
int num[N];
bool st[N];
int tiao[N];
int dui[N];
int dist[N];
int pre[N];
int n,m,s,d;

void dijkstra()
{
    dist[d] = 0;
    dui[d] = num[d];
    tiao[d] = 1;
    st[d] = true;

    for(int i = 0;i<n-1;i++)
    {
        //找最小边
        int t = -1;
        for(int j = 0;j<n;j++)if(!st[j] && (t==-1 || dist[t]>dist[j]))t = j;
        st[t] = true;
        //更新现有距离
        for(int j = 0;j<n;j++)
        {

            if( dist[j] > dist[t] + g[t][j])
            {
                tiao[j] = tiao[t];
                dist[j] = dist[t] + g[t][j];
                dui[j] = dui[t] + num[j];
                pre[j] = t;
            }
            else if( dist[j] == dist[t] + g[t][j])
            {
                tiao[j] += tiao[t];
                if(dui[j]<dui[t]+num[j])
                {
                    pre[j] = t;
                    dui[j] = dui[t] + num[j];
                }

            }
        }
    }
}

int main()
{
    memset(dist,0x3f,sizeof dist);
    memset(g,0x3f,sizeof g);//tmd 这里调了两小时，就因为没初始化
    cin>>n>>m>>s>>d;
    for(int i = 0; i< n;i++)cin>>num[i];
    while(m--)
    {
        int a,b,c;cin>>a>>b>>c;
        g[a][b] = g[b][a] = c;
    }
    dijkstra();

    cout<<tiao[s]<<' '<<dui[s]<<endl;
    for(int i = s;i!=d;i=pre[i])cout<<i<<' ';
    cout<<d;

    return 0;
}

//全过
稀疏图+堆优化

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int>PII;
const int N = 1000, M = N * N;
int h[N], ne[M], e[M], w[M], idx;
int n,m,s,d;
int num[N],dui[N],tiao[N];
int dist[N];
bool st[N];
int pre[N];

void add(int a,int b, int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dijkstra()
{
    dist[d] = 0;
    dui[d] = num[d];
    tiao[d] = 1;
    priority_queue<PII, vector<PII>, greater<PII> > q;
    q.push({0, d});
    while (q.size())
    {
        PII t = q.top();
        q.pop();
        int ver = t.second, distance = t.first;
        if (st[ver]) continue;          //重要 

        st[ver] = 1;        
        //用t更新其他节点的距离 
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                pre[j] = ver;                      //记录最短路路径 
                tiao[j] = tiao[ver];                  //最短路条数=上个点的条数
                dui[j] = dui[ver] + num[j];
                dist[j] = w[i] + distance;
                q.push({dist[j], j});               //只有找到了最短路的点入队列 
            } 
            else if (dist[j] == distance + w[i]) 
            {
                tiao[j] += tiao[ver];                  //最短路条数+上个点的条数
                if (dui[j] < dui[ver] + num[j])
                {
                    dui[j] = dui[ver] + num[j]; 
                    pre[j] = ver;                  //记录最短路路径 
                }
            }
        }
    }
}


int main()
{
    memset(dist,0x3f,sizeof dist);
    memset(h,-1,sizeof h);
    cin>>n>>m>>s>>d;
    for(int i =0;i<n;i++)cin>>num[i];
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }

    dijkstra();
    cout<<tiao[s]<<' '<<dui[s]<<endl;
    for(int i = s; i!=d;i=pre[i])cout<<i<<' ';
    cout<<d;
    return 0;
}

//未全过
稠密图堆优化

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int>PII;
const int N = 510;

int g[N][N];
int num[N];
bool st[N];
int tiao[N];
int dui[N];
int dist[N];
int pre[N];
int n,m,s,d;


void dijkstra()
{
    dist[d] = 0;
    dui[d] = num[d];
    tiao[d] = 1;
    priority_queue<PII, vector<PII>, greater<PII> > q;
    q.push({0, d});
    while (q.size())
    {
        PII t = q.top();
        q.pop();
        int ver = t.second, distance = t.first;
        if (st[ver]) continue;          //重要 

        st[ver] = 1;        
        //用t更新其他节点的距离 
        for (int j = 0; j<n;j++)
        {

            if (dist[j] > distance + g[ver][j])
            {
                pre[j] = ver;
                dui[j] = dui[ver] + num[j];
                dist[j] = g[ver][j] + distance;
                tiao[j] = tiao[ver];
                q.push({dist[j], j});               //只有找到了最短路的点入队列 
            } 
            else if (dist[j] == distance + g[ver][j]) 
            {
                if (dui[j] < dui[ver] + num[j])
                {
                    tiao[j] += tiao[ver];
                    dui[j] = dui[ver] + num[j]; 
                    pre[j] = ver;                  //记录最短路路径 
                }
            }
        }
    }
}

int main()
{
    memset(dist,0x3f,sizeof dist);
    memset(g,0x3f,sizeof g);//tmd 这里调了两小时，就因为没初始化
    cin>>n>>m>>s>>d;
    for(int i = 0; i< n;i++)cin>>num[i];
    while(m--)
    {
        int a,b,c;cin>>a>>b>>c;
        g[a][b] = g[b][a] = c;
    }
    dijkstra();

    cout<<tiao[s]<<' '<<dui[s]<<endl;
    for(int i = s;i!=d;i=pre[i])cout<<i<<' ';
    cout<<d;

    return 0;
}