L2-001. 紧急救援

L2-001. 紧急救援

题目链接：https://www.patest.cn/contests/gplt/L2-001

Dijstra

本题是dijstra的拓展，在求最短路的同时，增加了不同的最短路径的条数和能够召集的最多的救援队数量。由于初学此算法，我先找了题练习(http://poj.org/problem?id=2387)。

代码如下：

 #include<cstdio>

 #include<stack>

 #define N 505

 #define MAX 5000

 using namespace std;

 int n,m,s,d;

 int pro[N];

 int Map[N][N];

 bool mark[N];

 int sum[N];

 int path[N];

 int Distance[N];

 int person[N];

 int i,j;

 stack<int>st;

 int main(void){

     freopen("in.txt","r",stdin);

     scanf("%d%d%d%d",&n,&m,&s,&d);

     for(i=;i<n;++i)scanf("%d",&pro[i]);

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

         for(j=;j<n;++j)Map[i][j]=MAX;

     while(m--){

         int len;

         scanf("%d%d%d",&i,&j,&len);

         if(Map[i][j]>len)Map[i][j]=Map[j][i]=len;

     }

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

         Distance[i]=MAX;

         sum[i]=;

         person[i]=pro[s];

         if(Map[s][i]<MAX){

             Distance[i]=Map[s][i];

             path[i]=s;

             person[i]+=pro[i];

         }

     }

     mark[s]=,Distance[s]=;

     while(){

         int k,m=MAX;

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

             if(!mark[i]&&m>Distance[i]){

                 m=Distance[i];

                 k=i;

             }

         }

         if(m==MAX)break;

         mark[k]=;

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

             if(!mark[i]){

                 if(Distance[i]>Distance[k]+Map[k][i]){

                     Distance[i]=Distance[k]+Map[k][i];

                     person[i]=person[k]+pro[i];

                     path[i]=k;

                     sum[i]=sum[k];

                 }else if(Distance[i]==Distance[k]+Map[k][i]){

                     sum[i]+=sum[k];

                     if(person[i]<person[k]+pro[i]){

                         person[i]=person[k]+pro[i];

                         path[i]=k;

                     }

                 }

             }

         }

     }

     int temp=pro[d];

     int k=d;

     while(k!=s){

         st.push(k);

         k=path[k];

         temp+=pro[k];

     }

     printf("%d %d\n",sum[d],temp);

     printf("%d",s);

     while(!st.empty()){

         printf(" %d",st.top());

         st.pop();

     }

     printf("\n");

     return ;

 }

上面普通dijkstra算法的复杂度是O（n^2）的，而可以用优先队列将其优化到O（nlgn），代码如下：

 #include <iostream>

 #include <queue>

 #include <vector>

 #define N 505

 using namespace std;

 const int inf=0x3fffffff;

 int n,m,s,d,p[N],pre[N],dis[N],per[N],num[N];

 bool vis[N];

 struct edge{int to,w;};

 vector<edge>e[N];

 struct node{

     int u,d;

     bool operator < (const node x)const{return d>x.d;}

 };

 priority_queue<node>q;

 void dij(int s){

     for(int i=;i<n;++i)dis[i]=inf;

     dis[s]=;per[s]=p[s];num[s]=;pre[s]=-;

     q.push((node){s,});

     while(!q.empty()){

         node t=q.top();q.pop();

         int u=t.u;

         if(vis[u])continue;

         vis[u]=;

         for(int i=;i<(int)e[u].size();++i){

             int v=e[u][i].to,w=e[u][i].w;

             if(dis[u]+w==dis[v])num[v]+=num[u];

             if(dis[u]+w<dis[v])num[v]=num[u];

             if( (dis[u]+w==dis[v]&&per[u]+p[v]>per[v])

                ||dis[u]+w<dis[v]){

                 dis[v]=dis[u]+w;

                 per[v]=per[u]+p[v];

                 pre[v]=u;

                 q.push((node){v,dis[v]});

             }

         }

     }

 }

 void dfs(int k){

     if(k==-)return;

     dfs(pre[k]);

     cout<<k<<" ";

 }

 int main(void){

     std::ios::sync_with_stdio(false);

     cin>>n>>m>>s>>d;

     for(int i=;i<n;++i)cin>>p[i];

     for(int i=;i<m;++i){

         int u,v,w;

         cin>>u>>v>>w;

         e[u].push_back((edge){v,w});

         e[v].push_back((edge){u,w});

     }

     dij(s);

     cout<<num[d]<<" "<<per[d]<<"\n";

     dfs(pre[d]);

     cout<<d<<endl;

 }