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

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

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

  1 #include <stdio.h>
  2 #include <algorithm>
  3 #include <string.h>
  4 #include <vector>
  5 #include <map>
  6 #include <set>
  7 #include <queue>
  8 #include <iostream>
  9 #include <stdlib.h>
 10 #include <string>
 11 #include <stack>
 12 using namespace std;
 13 const int inf = 0x3f3f3f3f;
 14 typedef long long ll;
 15 typedef pair<int,int> pii;
 16 const int N = 500 + 5;
 17 
 18 int n,m,st,ed;
 19 int d[N],d2[N],val[N],pre[N];
 20 struct edge
 21 {
 22     int v,w;
 23 };
 24 vector<edge> G[N];
 25 
 26 void dij()
 27 {
 28     memset(pre,-1,sizeof(pre));
 29     memset(d,inf,sizeof(d));
 30     memset(d2,0,sizeof(d2));
 31     d[0]=0;
 32     d2[0]=val[0];
 33     priority_queue<pii,vector<pii>,greater<pii> > Q;
 34     Q.push(pii(0,0));
 35     while(!Q.empty())
 36     {
 37         pii x = Q.top();Q.pop();
 38         int u = x.second;
 39         int dis = x.first;
 40         if(d[u]<dis) continue;
 41         for(int i=0;i<G[u].size();i++)
 42         {
 43             edge& e = G[u][i];
 44             if(d[e.v] >= d[u]+e.w)
 45             {
 46                 if(d[e.v] > d[u]+e.w)
 47                 {
 48                     pre[e.v] = u;
 49                     d[e.v] = d[u]+e.w;
 50                     d2[e.v] = d2[u]+val[e.v];
 51                     Q.push(pii(d[e.v],e.v));
 52                 }
 53                 else
 54                 {
 55                     if(d2[e.v] < d2[u]+val[e.v])
 56                     {
 57                         pre[e.v] = u;
 58                         d2[e.v] = d2[u]+val[e.v];
 59                         Q.push(pii(d[e.v],e.v));
 60                     }
 61                 }
 62             }
 63         }
 64     }
 65 }
 66 
 67 int cnt = 0;
 68 bool vis[N];
 69 void dfs(int u,int dis)
 70 {
 71     if(u==ed && dis==d[ed]) {cnt++;return;}
 72     if(dis > d[ed]) return; // 剪枝！
 73     for(int i=0;i<G[u].size();i++)
 74     {
 75         edge& e = G[u][i];
 76         if(!vis[e.v])
 77         {
 78             vis[e.v]=1;
 79             dfs(e.v,dis+e.w);
 80             vis[e.v]=0;
 81         }
 82     }
 83 }
 84 
 85 void printAns(int now)
 86 {
 87     if(now != st) {printAns(pre[now]);printf(" ");}
 88     printf("%d",now);
 89 }
 90 
 91 int main()
 92 {
 93     while(scanf("%d%d%d%d",&n,&m,&st,&ed)==4)
 94     {
 95         for(int i=0;i<n;i++) {scanf("%d",val+i);G[i].clear();}
 96         while(m--)
 97         {
 98             int u,v,w;
 99             scanf("%d%d%d",&u,&v,&w);
100             G[u].push_back((edge){v,w});
101             G[v].push_back((edge){u,w});
102         }
103         dij();
104 
105         cnt = 0;memset(vis,0,sizeof(vis));
106         dfs(st,0);
107 
108         printf("%d %d
",cnt,d2[ed]);
109         printAns(ed);
110         puts("");
111     }
112 }

View Code

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

  1 #include <stdio.h>
  2 #include <algorithm>
  3 #include <string.h>
  4 #include <vector>
  5 #include <map>
  6 #include <set>
  7 #include <queue>
  8 #include <iostream>
  9 #include <stdlib.h>
 10 #include <string>
 11 #include <stack>
 12 using namespace std;
 13 const int inf = 0x3f3f3f3f;
 14 typedef long long ll;
 15 typedef pair<int,int> pii;
 16 const int N = 500 + 5;
 17 
 18 int n,m,st,ed;
 19 int d[N],d2[N],val[N],pre[N];
 20 set<int> p[N];
 21 struct edge
 22 {
 23     int v,w;
 24 };
 25 vector<edge> G[N];
 26 
 27 void dij()
 28 {
 29     memset(pre,-1,sizeof(pre));
 30     memset(d,inf,sizeof(d));
 31     memset(d2,0,sizeof(d2));
 32     d[0]=0;
 33     d2[0]=val[0];
 34     priority_queue<pii,vector<pii>,greater<pii> > Q;
 35     Q.push(pii(0,0));
 36     while(!Q.empty())
 37     {
 38         pii x = Q.top();Q.pop();
 39         int u = x.second;
 40         int dis = x.first;
 41         if(d[u]<dis) continue;
 42         for(int i=0;i<G[u].size();i++)
 43         {
 44             edge& e = G[u][i];
 45             if(d[e.v] >= d[u]+e.w)
 46             {
 47                 if(d[e.v] > d[u]+e.w)
 48                 {
 49                     p[e.v].clear();
 50                     p[e.v].insert(u);
 51 
 52                     pre[e.v] = u;
 53                     d[e.v] = d[u]+e.w;
 54                     d2[e.v] = d2[u]+val[e.v];
 55                     Q.push(pii(d[e.v],e.v));
 56                 }
 57                 else
 58                 {
 59                     p[e.v].insert(u);
 60 
 61                     if(d2[e.v] < d2[u]+val[e.v])
 62                     {
 63                         pre[e.v] = u;
 64                         d2[e.v] = d2[u]+val[e.v];
 65                         Q.push(pii(d[e.v],e.v));
 66                     }
 67                 }
 68             }
 69         }
 70     }
 71 }
 72 
 73 int cnt = 0;
 74 void dfs(int u)
 75 {
 76     if(u == st) {cnt++;return;}
 77     for(set<int>::iterator it=p[u].begin();it!=p[u].end();it++)
 78     {
 79         int v = *it;
 80         dfs(v);
 81     }
 82 }
 83 
 84 void printAns(int now)
 85 {
 86     if(now != st) {printAns(pre[now]);printf(" ");}
 87     printf("%d",now);
 88 }
 89 
 90 int main()
 91 {
 92     while(scanf("%d%d%d%d",&n,&m,&st,&ed)==4)
 93     {
 94         for(int i=0;i<n;i++) {scanf("%d",val+i);G[i].clear();}
 95         while(m--)
 96         {
 97             int u,v,w;
 98             scanf("%d%d%d",&u,&v,&w);
 99             G[u].push_back((edge){v,w});
100             G[v].push_back((edge){u,w});
101         }
102         dij();
103 
104         cnt = 0;
105         dfs(ed);
106 
107         printf("%d %d
",cnt,d2[ed]);
108         printAns(ed);
109         puts("");
110     }
111 }

View Code

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