PAT L2-001 紧急救援 —— （多参数最短路）

　　和天梯中的直捣黄龙差不多。但是，通过这个问题，我对多参数最短路又有了更深一层的了解。

　　这题因为点数比较多，所以如果直接用大力学长的在G上dfs找最短路径的条数的话，会TLE，所以需要剪枝。剪枝方法是，在dfs中当遇到dis>d[u]就直接return。具体见代码：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <iostream>

 #include <stdlib.h>

 #include <string>

 #include <stack>

 using namespace std;

 const int inf = 0x3f3f3f3f;

 typedef long long ll;

 typedef pair<int,int> pii;

 const int N =  + ;

 int n,m,st,ed;

 int d[N],d2[N],val[N],pre[N];

 struct edge

 {

     int v,w;

 };

 vector<edge> G[N];

 void dij()

 {

     memset(pre,-,sizeof(pre));

     memset(d,inf,sizeof(d));

     memset(d2,,sizeof(d2));

     d[]=;

     d2[]=val[];

     priority_queue<pii,vector<pii>,greater<pii> > Q;

     Q.push(pii(,));

     while(!Q.empty())

     {

         pii x = Q.top();Q.pop();

         int u = x.second;

         int dis = x.first;

         if(d[u]<dis) continue;

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

         {

             edge& e = G[u][i];

             if(d[e.v] >= d[u]+e.w)

             {

                 if(d[e.v] > d[u]+e.w)

                 {

                     pre[e.v] = u;

                     d[e.v] = d[u]+e.w;

                     d2[e.v] = d2[u]+val[e.v];

                     Q.push(pii(d[e.v],e.v));

                 }

                 else

                 {

                     if(d2[e.v] < d2[u]+val[e.v])

                     {

                         pre[e.v] = u;

                         d2[e.v] = d2[u]+val[e.v];

                         Q.push(pii(d[e.v],e.v));

                     }

                 }

             }

         }

     }

 }

 int cnt = ;

 bool vis[N];

 void dfs(int u,int dis)

 {

     if(u==ed && dis==d[ed]) {cnt++;return;}

     if(dis > d[ed]) return; // 剪枝！

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

     {

         edge& e = G[u][i];

         if(!vis[e.v])

         {

             vis[e.v]=;

             dfs(e.v,dis+e.w);

             vis[e.v]=;

         }

     }

 }

 void printAns(int now)

 {

     if(now != st) {printAns(pre[now]);printf(" ");}

     printf("%d",now);

 }

 int main()

 {

     while(scanf("%d%d%d%d",&n,&m,&st,&ed)==)

     {

         for(int i=;i<n;i++) {scanf("%d",val+i);G[i].clear();}

         while(m--)

         {

             int u,v,w;

             scanf("%d%d%d",&u,&v,&w);

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

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

         }

         dij();

         cnt = ;memset(vis,,sizeof(vis));

         dfs(st,);

         printf("%d %d\n",cnt,d2[ed]);

         printAns(ed);

         puts("");

     }

 }

　　当然，用我自己之前的方法也是可以的：用set型的p数组记录来时的点，再反向dfs即可。具体见代码：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <iostream>

 #include <stdlib.h>

 #include <string>

 #include <stack>

 using namespace std;

 const int inf = 0x3f3f3f3f;

 typedef long long ll;

 typedef pair<int,int> pii;

 const int N =  + ;

 int n,m,st,ed;

 int d[N],d2[N],val[N],pre[N];

 set<int> p[N];

 struct edge

 {

     int v,w;

 };

 vector<edge> G[N];

 void dij()

 {

     memset(pre,-,sizeof(pre));

     memset(d,inf,sizeof(d));

     memset(d2,,sizeof(d2));

     d[]=;

     d2[]=val[];

     priority_queue<pii,vector<pii>,greater<pii> > Q;

     Q.push(pii(,));

     while(!Q.empty())

     {

         pii x = Q.top();Q.pop();

         int u = x.second;

         int dis = x.first;

         if(d[u]<dis) continue;

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

         {

             edge& e = G[u][i];

             if(d[e.v] >= d[u]+e.w)

             {

                 if(d[e.v] > d[u]+e.w)

                 {

                     p[e.v].clear();

                     p[e.v].insert(u);

                     pre[e.v] = u;

                     d[e.v] = d[u]+e.w;

                     d2[e.v] = d2[u]+val[e.v];

                     Q.push(pii(d[e.v],e.v));

                 }

                 else

                 {

                     p[e.v].insert(u);

                     if(d2[e.v] < d2[u]+val[e.v])

                     {

                         pre[e.v] = u;

                         d2[e.v] = d2[u]+val[e.v];

                         Q.push(pii(d[e.v],e.v));

                     }

                 }

             }

         }

     }

 }

 int cnt = ;

 void dfs(int u)

 {

     if(u == st) {cnt++;return;}

     for(set<int>::iterator it=p[u].begin();it!=p[u].end();it++)

     {

         int v = *it;

         dfs(v);

     }

 }

 void printAns(int now)

 {

     if(now != st) {printAns(pre[now]);printf(" ");}

     printf("%d",now);

 }

 int main()

 {

     while(scanf("%d%d%d%d",&n,&m,&st,&ed)==)

     {

         for(int i=;i<n;i++) {scanf("%d",val+i);G[i].clear();}

         while(m--)

         {

             int u,v,w;

             scanf("%d%d%d",&u,&v,&w);

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

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

         }

         dij();

         cnt = ;

         dfs(ed);

         printf("%d %d\n",cnt,d2[ed]);

         printAns(ed);

         puts("");

     }

 }

　　想说明一点的是，我的方法跑的比大力学长的跑的快了2ms：他的46，我的44。。233= =。

巴特西

PAT L2-001 紧急救援 —— （多参数最短路）

最新文章

热门文章