A 1003
题意概述：最短路计数+求所有最短路当中给定的权值和最大的路径
只要在进行$dijkstra$ 时，更新一下松弛操作即可 $cnt[x]$记录达到当前节点最短路的条数 $ans[x]$表示到达该节点的最短路中的最大权值（打擂台更新）
if (d[y]>d[x]+z){
d[y]=d[x]+z;
cnt[y]=cnt[x];
ans[y]=a[y]+ans[x];
q.push(make_pair(-d[y],y));
}
else if (d[y]==d[x]+z){
cnt[y]+=cnt[x];
ans[y]=max(ans[y],ans[x]+a[y]);
}
注意点：linux测评 next是保留字 所以第一次CE了...
#include<bits/stdc++.h>
using namespace std;
int n,m,c1,c2,tot,head[250005],Next[250005],ver[250005],edge[250005],a[505],d[505],v[505],cnt[505],ans[505];
int s,t,x,y,z;
priority_queue<pair<int,int> >q;
void add(int x,int y,int z){
ver[++tot]=y;
edge[tot]=z;
Next[tot]=head[x];
head[x]=tot;
}
void dijkstra(){
memset(d,0x3f,sizeof(d));
memset(v,0,sizeof(v));
d[c1]=0;
q.push(make_pair(-d[c1],c1));
cnt[c1]=1;
ans[c1]=a[c1];
while (!q.empty()){
x=q.top().second;
q.pop();
if (v[x]) continue;
v[x]=1;
for (int i=head[x];i;i=Next[i]){
y=ver[i];
z=edge[i];
if (d[y]>d[x]+z){
d[y]=d[x]+z;
cnt[y]=cnt[x];
ans[y]=a[y]+ans[x];
q.push(make_pair(-d[y],y));
}
else if (d[y]==d[x]+z){
cnt[y]+=cnt[x];
ans[y]=max(ans[y],ans[x]+a[y]);
}
}
}
}
int main(){
scanf("%d%d%d%d",&n,&m,&c1,&c2);
for (int i=0;i<n;i++) scanf("%d",&a[i]);
for (int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);//无向边
}
dijkstra();
printf("%d %d
",cnt[c2],ans[c2]);
return 0;
}