【PAT甲级】1003 Emergency (25 分)（SPFA,DFS）

题意：n个点，m条双向边，每条边给出通过用时，每个点给出点上的人数，给出起点终点，求不同的最短路的数量以及最短路上最多能通过多少人。(N<=500)

AAAAAccepted code：

 #include<bits/stdc++.h>

 using namespace std;

 int n,m;

 int s,t;

 int a[];

 vector<pair<int,int> >adj[];

 vector<int>pre[];

 vector<int>tmp_path;

 int ans=;

 int d[];

 bool inq[];

 int sum=;

 void SPFA(){

     queue<int>q;

     for(int i=;i<n;++i)

        d[i]=1e9;

     d[s]=;

     q.push(s);

     inq[s]=;

     while(!q.empty()){

         int u=q.front();

         q.pop();

         inq[u]=;

         for(int i=;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]=;

                 }

             }

             else if(d[u]+l==d[v])

                 pre[v].push_back(u);

         }

     }

 }

 void DFS(int x){

     if(x==s){

         int tmp=;

         for(int i=tmp_path.size()-;i>=;--i){

             int u=tmp_path[i];

             tmp+=a[u];

         }

         if(tmp>ans)

             ans=tmp;

     }

     else

         sum+=pre[x].size()-;

     tmp_path.push_back(x);

     for(int i=;i<pre[x].size();++i)

         DFS(pre[x][i]);

     tmp_path.pop_back();

 }

 int main(){

     cin>>n>>m>>s>>t;

     for(int i=;i<n;++i)

         cin>>a[i];

     for(int i=;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);

     cout<<sum<<" "<<ans+a[s];

     return ;

 }