题意：n个点，m条双向边，每条边给出通过用时，每个点给出点上的人数，给出起点终点，求不同的最短路的数量以及最短路上最多能通过多少人。(N<=500)
AAAAAccepted code：
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m; 4 int s,t; 5 int a[507]; 6 vector<pair<int,int> >adj[507]; 7 vector<int>pre[507]; 8 vector<int>tmp_path; 9 int ans=0; 10 int d[507]; 11 bool inq[507]; 12 int sum=1; 13 void SPFA(){ 14 queue<int>q; 15 for(int i=0;i<n;++i) 16 d[i]=1e9; 17 d[s]=0; 18 q.push(s); 19 inq[s]=1; 20 while(!q.empty()){ 21 int u=q.front(); 22 q.pop(); 23 inq[u]=0; 24 for(int i=0;i<adj[u].size();++i){ 25 int v=adj[u][i].first; 26 int l=adj[u][i].second; 27 if(d[u]+l<d[v]){ 28 d[v]=d[u]+l; 29 pre[v].clear(); 30 pre[v].push_back(u); 31 if(!inq[v]){ 32 q.push(v); 33 inq[v]=1; 34 } 35 } 36 else if(d[u]+l==d[v]) 37 pre[v].push_back(u); 38 } 39 } 40 } 41 void DFS(int x){ 42 if(x==s){ 43 int tmp=0; 44 for(int i=tmp_path.size()-1;i>=0;--i){ 45 int u=tmp_path[i]; 46 tmp+=a[u]; 47 } 48 if(tmp>ans) 49 ans=tmp; 50 } 51 else 52 sum+=pre[x].size()-1; 53 tmp_path.push_back(x); 54 for(int i=0;i<pre[x].size();++i) 55 DFS(pre[x][i]); 56 tmp_path.pop_back(); 57 } 58 int main(){ 59 cin>>n>>m>>s>>t; 60 for(int i=0;i<n;++i) 61 cin>>a[i]; 62 for(int i=0;i<m;++i){ 63 int x,y,w; 64 cin>>x>>y>>w; 65 adj[x].push_back({y,w}); 66 adj[y].push_back({x,w}); 67 } 68 SPFA(); 69 DFS(t); 70 cout<<sum<<" "<<ans+a[s]; 71 return 0; 72 }