前言
首先使用一下模板，所有答案都在solve中：
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)//不能使用scanf了
#define int long long
#define MAX INT_MAX/2
#define MIN INT_MIN/2
const int mod=1e9 + 7;
const int N = 1e6 + 7;#define loop(n) for(int i=0;i<n;i++)
#define For(x,a,b) for(int x=a;x<=b;x++)
#define rFor(x,a,b) for(int x=a;x>=b;x--)#define lowbit(x) (x&(-x))
#define pii pair<int,int>
#define mem(a,x) memset(a,x,sizeof a)
//memset只推荐使用0和-1#define print(c) cout<<""#c": "<<c<<endl;
#define printt(a,b) cout<<""#a": "<<a<<'-'<<""#b": "<<b<<endl;
#define printtt(a,b,c) \cout<<""#a": "<<a<<'-'<<""#b": "<<b<<'-'<<""#c":"<<c<<endl;
#define prinT(s) {for(auto i:s)cout<<i<<' ';cout<<endl;}
using namespace std;
void solve();
signed main() {ios;int n = 1;//cin >> n;while (n--)solve();
}
/*solve:*/
void solve(){}
题目
1003 Emergency - PAT (Advanced Level) Practice (pintia.cn)
/*solve:
再dj算法的基础上加上了价值value
要特别注意的是这里要求的cnt是指到这个点的路径种类数，即有多少种方法到达这个点
*/
void solve(){int n,m,from,to;cin>>n>>m>>from>>to;int value[n];loop(n)cin>>value[i];map<int,map<int,int>> g;loop(m){int a,b,c;cin>>a>>b>>c;if(g[a][b]==0)g[a][b]=c;else g[a][b]=min(g[a][b],c);g[b][a]=g[a][b];}int d[n+1],st[n+1],v[n+1],cnt[n+1];//cnt为数量，v为到这里时集齐的队伍人数loop(n+1)d[i]=MAX,st[i]=0,v[i]=0,cnt[i]=0;//1入队d[from]=0,cnt[from]=1,v[from]=value[from];loop(n){//这个是单源最短路，如果有相同消耗但是到同一个位置的value不一样，选择大的valueint t=-1;For(j,0,n-1)if(!st[j]&&(t==-1||d[j]<d[t]))t=j;// print(t);if(st[t]==0)st[t]=1;else continue;for(auto it:g[t]){//不变和经过t这2个情况int j=it.first,w=d[t]+it.second;if(d[j]==w){//如果相同的话，比较哪个带来的价值更大v[j]=max(v[t]+value[j],v[j]);cnt[j]+=cnt[t];}if(w<d[j])//如果有更新最短路d[j]=w,v[j]=v[t]+value[j],cnt[j]=cnt[t];}}cout<<cnt[to]<<' '<<v[to]<<endl;
}
如果要看思路的话，点这个： https://kimi.moonshot.cn/share/croeqne0atp7tffgcnf0
