题目链接：https://pintia.cn/problem-sets/994805046380707840/problems/994805073643683840
题目大意：就是让你找一个单源最短路，同时还需要能够输出最短路的路径
输入：
第一行n,m,s,d，分别是城市数，路径数，起点，终点。
第二行n个数，是每个城市有的救援队的数目
接下来m行就是每条道路的两个端点和长度
输出：
第一行输出最短路径条数和救援队数量，第二行就是从起点到终点的路径。
分析：本质上还是用dij做的最短路问题，但需要添加些东西，我们可以用num数组表示从起点到i的最短路径条数，w数组表示救援队数量
同时最用dij做最短路的时候，把最短路径上每个城市的前驱用pre数组记录下来
这样，在更新最短路时，如果dis[e.to]>dis[v]+e.cost 就需要将v和e.to连接起来，那么num[e.to]就应该和num[v]保持一致，w[e.to]=w[v]+a[e.to]
除了大于的情况，对于dis[e.to]==dis[v]+e.cost，我们也需要考虑，因为e.to的最短路径条数除了本身的，还有从v连接过来的，则num[e.to]+=num[v]
如果w[v]+a[e.to]>w[e.to]，那么w[e.to]=w[v]+a[e.to]，因为要保证救援队数量最多
另外每当连路径的时候记得把pre数组录入一下，最后递归输出即可
#include <bits/stdc++.h>
using namespace std;
const int inf=<<;
typedef long long ll;
typedef pair<int,int> P;
const double pi=acos(-);
const int mod=1e8+;
const int maxn=;
const int maxm=;
int dis[maxn];
int a[maxn],num[maxn],w[maxn],pre[maxn];//num数组是出发点到i点时拥有的路径的条数，w数组是救援队的数目
struct edge{
int to,cost;
};
int x,y,z,n,m,s,d;
vector<edge> g[maxm];
void dij(int s){
priority_queue<P,vector<P>,greater<P> > que;
fill(dis,dis+maxn,inf);
dis[s]=;
w[s]=a[s],num[s]=;//初始化，到起始点救援队数量就是起始点本身救援队数量，路径也只有一条
que.push({,s});
while(!que.empty()){
P p=que.top();que.pop();
int v=p.second;
if(dis[v]<p.first) continue;
for(int i=;i<g[v].size();i++){
edge e=g[v][i];
if(dis[e.to]>dis[v]+e.cost){//这种情况肯定要从v到e.to了
num[e.to]=num[v];
w[e.to]=w[v]+a[e.to];
dis[e.to]=dis[v]+e.cost;
pre[e.to]=v;
que.push({dis[e.to],e.to});
}
else if(dis[e.to]==dis[v]+e.cost){
if(w[v]+a[e.to]>w[e.to]){w[e.to]=w[v]+a[e.to];pre[e.to]=v;}
num[e.to]+=num[v]; //还要再加上v点的
}
}
}
}
void print(int c){
if(c==s){
cout<<s;return;
}
print(pre[c]);
cout<<" "<<c;
}
int main(){
scanf("%d%d%d%d",&n,&m,&s,&d);
for(int i=;i<n;i++) scanf("%d",&a[i]);
for(int i=;i<m;i++){
scanf("%d%d%d",&x,&y,&z);
g[x].push_back({y,z});
g[y].push_back({x,z});
}
dij(s);
cout<<num[d]<<" "<<w[d]<<endl;
print(d);
cout<<endl;
return ;
}