题意：n个点，m条双向边，每条边给出通过用时，每个点给出点上的人数，给出起点终点，求不同的最短路的数量以及最短路上最多能通过多少人。(N<=500)
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
int s,t;
int a[507];
vector<pair<int,int> >adj[507];
vector<int>pre[507];
vector<int>tmp_path;
int ans=0;
int d[507];
bool inq[507];
int sum=1;
void SPFA(){
queue<int>q;
for(int i=0;i<n;++i)
d[i]=1e9;
d[s]=0;
q.push(s);
inq[s]=1;
while(!q.empty()){
int u=q.front();
q.pop();
inq[u]=0;
for(int i=0;i<adj[u].size();++i){
int v=adj[u][i].first;
int l=adj[u][i].second;
if(d[u]+l<d[v]){
d[v]=d[u]+l;
pre[v].clear();
pre[v].push_back(u);
if(!inq[v]){
q.push(v);
inq[v]=1;
}
}
else if(d[u]+l==d[v]){
pre[v].push_back(u);
}
}
}
}
void DFS(int x){
if(x==s){
int tmp=0;
for(int i=tmp_path.size()-1;i>=0;--i){
int u=tmp_path[i];
tmp+=a[u];
}
if(tmp>ans)
ans=tmp;
}
else
sum+=pre[x].size()-1;
tmp_path.push_back(x);
for(int i=0;i<pre[x].size();++i)
DFS(pre[x][i]);
tmp_path.pop_back();
}
int main(){
cin>>n>>m>>s>>t;
for(int i=0;i<n;++i)
cin>>a[i];
for(int i=0;i<m;++i){
int x,y,w;
cin>>x>>y>>w;
adj[x].push_back({y,w});
adj[y].push_back({x,w});
}
SPFA();
DFS(t);
/*for(int i=0;i<n;++i){
cout<<i<<endl;
for(int j=0;j<pre[i].size();++j){
cout<<pre[i][j]<<endl;
}
cout<<endl;
}*/
cout<<sum<<" "<<ans+a[s];
return 0;
}
【PAT甲级】1003 Emergency (25 分)（SPFA,DFS）
原文：https://www.cnblogs.com/ldudxy/p/11194106.html