2016团体程序设计天梯赛-决赛-部分题解

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

　　第一个卡的题是“到底是不是太胖了”，当时以为卡精度，因为各种eps都过不了。。但是结束后队友说不卡精度，随便一个eps就过了- -，可能是代码写搓了。但是更好的方法是全部变成整数做来规避精度的问题。具体见代码：

 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 using namespace std;
10 const int inf = 0x3f3f3f3f;
11 typedef long long ll;
12 const int N = 500 + 5;
13 
14 int main()
15 {
16     int T;
17     cin >> T;
18     while(T--)
19     {
20         int h,w;
21         cin >> h >> w;
22         int biaozhun = 2*(h-100);
23         if(w*100>biaozhun*9*9 && w*100<biaozhun*11*9) puts("You are wan mei!");
24         else if(w*100>=biaozhun*11*9) puts("You are tai pang le!");
25         else puts("You are tai shou le!");
26     }
27 }

View Code

　　然后是红色警报这题，一开始以为是和上次的删边并查集一样，但是比赛时发现没法做，比赛结束后仓鼠学长说可以并查集做，但是他没有通过全部数据。。但是考虑到这题的数据范围小，可以直接暴力做，每次删除一个点就判断一下连通分量数的变化即可。具体见代码（细节比较多）：

 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 using namespace std;
10 const int inf = 0x3f3f3f3f;
11 typedef long long ll;
12 const int N = 500 + 5;
13 
14 vector<int> G[N];
15 int root[N];
16 bool vis[N],des[N];
17 int findroot(int x) {return x==root[x]?x:root[x]=findroot(root[x]);}
18 int n,m,k;
19 
20 void dfs(int x)
21 {
22     vis[x] = 1;
23     for(int i=0;i<G[x].size();i++)
24     {
25         int v = G[x][i];
26         if(des[v] || vis[v]) continue;
27         dfs(v);
28     }
29 }
30 
31 int getcnt()
32 {
33     int cnt = 0;
34     memset(vis,0,sizeof(vis));
35     for(int i=0;i<n;i++)
36     {
37         if(!des[i] && !vis[i]) {dfs(i);cnt++;
38         //printf("%d !!
",i);
39         }
40     }
41     return cnt;
42 }
43 
44 int main()
45 {
46     while(scanf("%d%d",&n,&m)==2)
47     {
48         memset(des,false,sizeof(des));
49         for(int i=1;i<=n;i++) G[i].clear(),root[i]=i;
50         for(int i=1;i<=m;i++)
51         {
52             int u,v;
53             scanf("%d%d",&u,&v);
54             G[u].push_back(v);
55             G[v].push_back(u);
56         }
57         int cnt = getcnt();
58         scanf("%d",&k);
59         /*if(n==1 && k==1)
60         {
61             int t;
62             scanf("%d",&t);
63             printf("Red Alert: ");
64             printf("City %d is lost!
",t);
65             printf("Game Over.
");
66             continue;
67         }*/
68         for(int i=1;i<=k;i++)
69         {
70             int t;
71             scanf("%d",&t);
72             des[t] = 1;
73             int now = getcnt();
74             if(G[t].size()==0) cnt--;
75             // 只有一个点的联通分量被删除，不会发生警报
76             //printf("%d %d !!
",cnt,now);
77 
78             //now = cnt;
79             if(now > cnt)
80             {
81                 printf("Red Alert: ");
82                 printf("City %d is lost!
",t);
83             }
84             else printf("City %d is lost.
",t);
85             if(now != cnt) cnt = now; // 存在有now小于cnt的可能性
86 
87             if(i==n) printf("Game Over.
");
88         }
89     }
90 }

View Code

　　列车调度，比赛时想的方法是弄一个set数组，然后不断的把新元素插入到可以插入的位置并且满足这个元素比set的首元素小，比方说已经有的三个set是{7}{8}{9}，那么新元素是4的话那么就插入到7的前面（如果不存在这样的set就新开一个set），然后答案就是开的set的个数，不过这个方法有很大的问题，想了一下，如果存在多个可以放的位置，到底放哪个很难讲清楚：举个例子有集合{7}{9}，我要插入4，应该是插在7后面比较好，因为这样的话如果再插入一个元素8就可以放在9的后面不必新开set；如果4放9后，8就得新开set了。那么是不是如果有多个可以放的位置放在首元素最小的位置就可以了呢？这样的话仍会超时，因为每次插入一个新的元素的复杂度是O(n)。

　　所以，这题的正解是LIS。试想，这个题目的意思是，让一个序列经过调度以后变成递增的，那么需要调度的是这个序列里面原先递减的部分，所以只要求原序列里面最长递减子序列的长度即可，这个序列的每一个元素都需要放进一个轨道，然后原序列中递增的元素按照原先的顺序插入到能插入的位置即可，因为他们的相对位置是递增，出来也一定是递增的（其实这么一想的话和用set维护的原理还是差不多的）。然后，考虑道题目给的序列顺序是从右到左的，因此求的是最长上升子序列的长度，即LIS。具体见代码：

 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 using namespace std;
10 const int inf = 0x3f3f3f3f;
11 typedef long long ll;
12 const int N = (int)1e5 + 5;
13 
14 int dp[N];
15 
16 int main()
17 {
18     int n;
19     while(scanf("%d",&n)==1)
20     {
21         memset(dp,inf,sizeof(dp));
22         for(int i=0;i<n;i++)
23         {
24             int v;
25             scanf("%d",&v);
26             *lower_bound(dp,dp+n,v) = v;
27         }
28         printf("%d
",lower_bound(dp,dp+n,inf)-dp);
29     }
30 }

View Code

　　二叉搜索树那题，让你判断这棵树是不是完全的二叉树。虽然别人都说简单，但是我不会写二叉树，所以这里也还是留个代码吧：

 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 using namespace std;
10 const int inf = 0x3f3f3f3f;
11 typedef long long ll;
12 const int N = (int)1e6 + 5;
13 
14 int tree[N];
15 
16 int main()
17 {
18     int n;
19     while(scanf("%d",&n)==1)
20     {
21         memset(tree,inf,sizeof(tree));
22         int maxpos = 1;
23         for(int i=1;i<=n;i++)
24         {
25             int v;
26             scanf("%d",&v);
27             int pos = 1;
28             while(tree[pos] != inf)
29             {
30                 if(v > tree[pos]) pos = pos << 1;
31                 else pos = pos << 1 | 1;
32             }
33             tree[pos] = v;
34             maxpos = max(maxpos,pos);
35         }
36 
37         /*
38             若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，
39             第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
40             
41             满二叉树：除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上。
42         */
43         int flag = 1,first = 1;
44         for(int i=1;i<=maxpos;i++)
45         {
46             if(tree[i] != inf)
47             {
48                 if(first)
49                 {
50                     printf("%d",tree[i]);
51                     first = 0;
52                 }
53                 else printf(" %d",tree[i]);
54             }
55             else flag = 0;
56         }
57 
58         puts("");
59         puts(flag?"YES":"NO");
60     }
61 }

View Code

　　愿天下有情人都是失散多年的兄妹，这题当时做的人挺少以为很难，其实还是比较简单的，也不用什么LCA，直接暴力一下访问5代就行了，但是有个坑点是，在建图时对父母进行push_back的时候，父母的性别在这个时候也要设置好。具体见代码：

 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 using namespace std;
11 const int inf = 0x3f3f3f3f;
12 typedef long long ll;
13 const int N = (int)1e5 + 5;
14 
15 vector<int> G[N];
16 bool sex[N],vis[N];
17 bool have;
18 
19 void dfs(int u,int deep)
20 {
21     if(deep == 6) return;
22     if(vis[u]) {have = true;return;}
23     vis[u] = 1;
24     for(int i=0;i<G[u].size();i++)
25     {
26         dfs(G[u][i],deep+1);
27     }
28 }
29 
30 int main()
31 {
32     int n,k;
33     scanf("%d",&n);
34     for(int i=1;i<=n;i++)
35     {
36         char s1[10],s2[10],s3[10],s4[10];
37         scanf("%s%s%s%s",s1,s2,s3,s4);
38         if(atoi(s3) != -1) G[atoi(s1)].push_back(atoi(s3)),sex[atoi(s3)]=1;
39         if(atoi(s4) != -1) G[atoi(s1)].push_back(atoi(s4)),sex[atoi(s4)]=0;
40         sex[atoi(s1)] = s2[0]=='M';
41     }
42 
43     scanf("%d",&k);
44     for(int i=1;i<=k;i++)
45     {
46         char s1[10],s2[10];
47         scanf("%s%s",s1,s2);
48         int x = atoi(s1),y = atoi(s2);
49 
50         have = false;
51         memset(vis,0,sizeof(vis));
52         dfs(x,1);
53         dfs(y,1);
54         if(sex[x] == sex[y]) puts("Never Mind");
55         else if(have) puts("No");
56         else puts("Yes");
57     }
58 }

View Code

　　直捣黄龙。这题是最短路的一个变种。可以使用当时省赛那题的方法，不过有一组数据WA了，，也不知道为什么- -。然后我用dfs乱搞，结果AC了。这题也算是最短路的一个好题了吧。具体见代码（上面的一份是WA了一组的，下面的是AC的）：

  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 = 200 + 5;
 17 
 18 struct edge
 19 {
 20     int v,w;
 21     int kill;
 22 };
 23 vector<edge> G[N];
 24 edge pre[N];
 25 vector<edge> p[N];
 26 int d[N],cnt[N],d2[N],d3[N];
 27 map<string,int> M;
 28 map<int,string> M2;
 29 
 30 void dij()
 31 {
 32     memset(d,inf,sizeof(d));
 33     memset(d2,0,sizeof(d2));
 34     memset(d3,0,sizeof(d3));
 35     d[1] = 0;
 36     d2[1] = 0;
 37     d3[1] = 0;
 38     priority_queue<pii,vector<pii>,greater<pii> > Q;
 39     Q.push(pii(0,1));
 40     while(!Q.empty())
 41     {
 42         pii x = Q.top();Q.pop();
 43         int u = x.second;
 44         int dis = x.first;
 45         if(d[u] != dis) continue;
 46         for(int i=0;i<G[u].size();i++)
 47         {
 48             edge e = G[u][i];
 49             if(d[e.v] >= d[u]+e.w)
 50             {
 51                 if(d[e.v] > d[u]+e.w)
 52                 {
 53                     d[e.v] = d[u]+e.w;
 54                     d2[e.v] = d2[u]+1;
 55                     d3[e.v] = d3[u]+e.kill;
 56                     Q.push(pii(d[e.v],e.v));
 57                     pre[e.v] = (edge){u};
 58 
 59                     p[e.v].clear();
 60                     p[e.v].push_back((edge){u});
 61                 }
 62                 else
 63                 {
 64                     p[e.v].push_back((edge){u});
 65 
 66                     if(d2[e.v] <= d2[u]+1)
 67                     {
 68                         if(d2[e.v] < d2[u]+1)
 69                         {
 70                             d[e.v] = d[u]+e.w;
 71                             d2[e.v] = d2[u]+1;
 72                             d3[e.v] = d3[u]+e.kill;
 73                             Q.push(pii(d[e.v],e.v));
 74                             pre[e.v] = (edge){u};
 75                         }
 76                         else
 77                         {
 78                             if(d3[e.v] <= d3[u]+e.kill)
 79                             {
 80                                 if(d3[e.v] < d3[u]+e.kill)
 81                                 {
 82                                     d[e.v] = d[u]+e.w;
 83                                     d2[e.v] = d2[u]+1;
 84                                     d3[e.v] = d3[u]+e.kill;
 85                                     Q.push(pii(d[e.v],e.v));
 86                                     pre[e.v] = (edge){u};
 87                                 }
 88                             }
 89                         }
 90                     }
 91                 }
 92             }
 93         }
 94     }
 95 }
 96 
 97 int Cnt=0;
 98 void dfs(int u)
 99 {
100     if(u==1) {Cnt++;return;}
101     for(int i=0;i<p[u].size();i++)
102     {
103         edge e = p[u][i];
104         dfs(e.v);
105     }
106 }
107 
108 int main()
109 {
110     int n,k,tot=0;
111     scanf("%d%d",&n,&k);
112     string st,ed;
113     cin >> st >> ed;
114     M[st] = 1;
115     M2[1] = st;
116     cnt[1] = 0;
117     for(int i=2;i<=n;i++)
118     {
119         string s;
120         cin >> s >> cnt[i];
121         M[s] = i;
122         M2[i] = s;
123     }
124     scanf("%d",&k);
125     while(k--)
126     {
127         string u,v;
128         int w;
129         cin >> u >> v >> w;
130         G[M[u]].push_back((edge){M[v],w,cnt[M[v]]});
131         G[M[v]].push_back((edge){M[u],w,cnt[M[u]]});
132     }
133 
134     dij();
135     dfs(M[ed]);
136 
137     vector<string> ans;
138     int now = M[ed];
139     while(now != 1)
140     {
141         ans.push_back(M2[now]);
142         now = pre[now].v;
143     }
144     ans.push_back(st);
145 
146     for(int i=ans.size()-1;i>=0;i--)
147     {
148         if(i!=ans.size()-1) printf("->");
149         cout << ans[i];
150     }
151     puts("");
152     printf("%d %d %d
",Cnt,d[M[ed]],d3[M[ed]]);
153 }

View Code

  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 = 200 + 5;
 17 
 18 struct edge
 19 {
 20     int v,w;
 21 };
 22 struct way
 23 {
 24     int p_cnt,kill;
 25     bool operator < (const way& A)const
 26     {
 27         return p_cnt==A.p_cnt?kill>A.kill:p_cnt>A.p_cnt;
 28     }
 29 };
 30 vector<edge> G[N];
 31 vector<edge> p[N];
 32 vector<way> W;
 33 int d[N],cnt[N];
 34 map<string,int> M;
 35 map<int,string> M2;
 36 
 37 void dij()
 38 {
 39     memset(d,inf,sizeof(d));
 40     d[1] = 0;
 41     priority_queue<pii,vector<pii>,greater<pii> > Q;
 42     Q.push(pii(0,1));
 43     while(!Q.empty())
 44     {
 45         pii x = Q.top();Q.pop();
 46         int u = x.second;
 47         int dis = x.first;
 48         if(d[u] != dis) continue;
 49         for(int i=0;i<G[u].size();i++)
 50         {
 51             edge e = G[u][i];
 52             if(d[e.v] >= d[u]+e.w)
 53             {
 54                 if(d[e.v] > d[u]+e.w)
 55                 {
 56                     d[e.v] = d[u]+e.w;
 57                     Q.push(pii(d[e.v],e.v));
 58                     p[e.v].clear();
 59                     p[e.v].push_back((edge){u,e.w});
 60                 }
 61                 else p[e.v].push_back((edge){u,e.w});
 62             }
 63         }
 64     }
 65 }
 66 
 67 int Cnt=0;
 68 void dfs(int u,int p_cnt,int kill)
 69 {
 70     if(u==1) {Cnt++;W.push_back((way){p_cnt,kill});return;}
 71     for(int i=0;i<p[u].size();i++)
 72     {
 73         edge e = p[u][i];
 74         dfs(e.v,p_cnt+1,kill+cnt[e.v]);
 75     }
 76 }
 77 
 78 int A,B;
 79 vector<string> ans;
 80 void findAns(int u,int p_cnt,int kill)
 81 {
 82     if(u==1)
 83     {
 84         if(A==p_cnt && B==kill)
 85         {
 86             for(int i=ans.size()-1;i>=0;i--)
 87             {
 88                 if(i!=ans.size()-1) printf("->");
 89                 cout<<ans[i];
 90             }
 91             puts("");
 92 
 93             return;
 94         }
 95         else return;
 96     }
 97     for(int i=0;i<p[u].size();i++)
 98     {
 99         edge e = p[u][i];
100         ans.push_back(M2[e.v]);
101         findAns(e.v,p_cnt+1,kill+cnt[e.v]);
102         ans.erase(ans.end());
103     }
104 }
105 
106 int main()
107 {
108     int n,k,tot=0;
109     scanf("%d%d",&n,&k);
110     string st,ed;
111     cin >> st >> ed;
112     M[st] = 1;
113     M2[1] = st;
114     cnt[1] = 0;
115     for(int i=2;i<=n;i++)
116     {
117         string s;
118         cin >> s >> cnt[i];
119         M[s] = i;
120         M2[i] = s;
121     }
122     scanf("%d",&k);
123     while(k--)
124     {
125         string u,v;
126         int w;
127         cin >> u >> v >> w;
128         G[M[u]].push_back((edge){M[v],w});
129         G[M[v]].push_back((edge){M[u],w});
130     }
131 
132     dij();
133 
134     dfs(M[ed],0,cnt[M[ed]]);
135     sort(W.begin(),W.end());
136 
137     A=W[0].p_cnt,B=W[0].kill;
138     ans.push_back(ed);
139     findAns(M[ed],0,cnt[M[ed]]);
140 
141     printf("%d %d %d
",Cnt,d[M[ed]],W[0].kill);
142 }

View Code

值得注意的是，在写完以后我发现用来记录最短路边的pre数组，只需要记录来时候的点就够了。

————————————伟大的分界线——————————————

　　这里是第二天的时候补充的，因为找到上面的第一份代码为何错了。

　　原因在于用于记录某点的各种最短路中到达这个点的点（即p数组记录的点）有重复，导致最短路径的误判。

　　举个例子如下：

　　用第一种方法的话，因为即使dis相同，点也要入优先队列，那么以上图为例，D就被入队了两次。从而E的p数组中储存了两个D，这样在使用p数组进行反向dfs的时候，路径数就会出错了。

　　解决方法的话有两个。第一，p数组的含义是可以完成最短路中的到达这个点的不同的点，那么用set来储存p数组即可。代码如下：

  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 = 200 + 5;
 17 
 18 struct edge
 19 {
 20     int v,w;
 21     int kill;
 22 };
 23 vector<edge> G[N];
 24 edge pre[N];
 25 set<int> p[N];
 26 int d[N],cnt[N],d2[N],d3[N];
 27 map<string,int> M;
 28 map<int,string> M2;
 29 
 30 void dij()
 31 {
 32     memset(d,inf,sizeof(d));
 33     memset(d2,0,sizeof(d2));
 34     memset(d3,0,sizeof(d3));
 35     d[1] = 0;
 36     d2[1] = 0;
 37     d3[1] = 0;
 38     priority_queue<pii,vector<pii>,greater<pii> > Q;
 39     Q.push(pii(0,1));
 40     while(!Q.empty())
 41     {
 42         pii x = Q.top();Q.pop();
 43         int u = x.second;
 44         int dis = x.first;
 45         if(d[u] != dis) continue;
 46         for(int i=0;i<G[u].size();i++)
 47         {
 48             edge e = G[u][i];
 49             if(d[e.v] >= d[u]+e.w)
 50             {
 51                 if(d[e.v] > d[u]+e.w)
 52                 {
 53                     d[e.v] = d[u]+e.w;
 54                     d2[e.v] = d2[u]+1;
 55                     d3[e.v] = d3[u]+e.kill;
 56                     Q.push(pii(d[e.v],e.v));
 57                     pre[e.v] = (edge){u};
 58 
 59                     p[e.v].clear();
 60                     p[e.v].insert(u);
 61                 }
 62                 else
 63                 {
 64                     p[e.v].insert(u);
 65 
 66                     if(d2[e.v] <= d2[u]+1)
 67                     {
 68                         if(d2[e.v] < d2[u]+1)
 69                         {
 70                             d[e.v] = d[u]+e.w;
 71                             d2[e.v] = d2[u]+1;
 72                             d3[e.v] = d3[u]+e.kill;
 73                             Q.push(pii(d[e.v],e.v));
 74                             pre[e.v] = (edge){u};
 75                         }
 76                         else
 77                         {
 78                             if(d3[e.v] <= d3[u]+e.kill)
 79                             {
 80                                 if(d3[e.v] < d3[u]+e.kill)
 81                                 {
 82                                     d[e.v] = d[u]+e.w;
 83                                     d2[e.v] = d2[u]+1;
 84                                     d3[e.v] = d3[u]+e.kill;
 85                                     Q.push(pii(d[e.v],e.v));
 86                                     pre[e.v] = (edge){u};
 87                                 }
 88                             }
 89                         }
 90                     }
 91                 }
 92             }
 93         }
 94     }
 95 }
 96 
 97 int Cnt=0;
 98 bool vis[N];
 99 void dfs(int u)
100 {
101     if(u==1) {Cnt++;return;}
102     for(set<int>::iterator it=p[u].begin();it!=p[u].end();it++)
103     {
104         int v = *it;
105         dfs(v);
106     }
107 }
108 
109 int main()
110 {
111     int n,k,tot=0;
112     scanf("%d%d",&n,&k);
113     string st,ed;
114     cin >> st >> ed;
115     M[st] = 1;
116     M2[1] = st;
117     cnt[1] = 0;
118     for(int i=2;i<=n;i++)
119     {
120         string s;
121         cin >> s >> cnt[i];
122         M[s] = i;
123         M2[i] = s;
124     }
125     scanf("%d",&k);
126     while(k--)
127     {
128         string u,v;
129         int w;
130         cin >> u >> v >> w;
131         G[M[u]].push_back((edge){M[v],w,cnt[M[v]]});
132         G[M[v]].push_back((edge){M[u],w,cnt[M[u]]});
133     }
134 
135     dij();
136     memset(vis,0,sizeof(vis));
137     dfs(M[ed]);
138 
139     vector<string> ans;
140     int now = M[ed];
141     while(now != 1)
142     {
143         ans.push_back(M2[now]);
144         now = pre[now].v;
145     }
146     ans.push_back(st);
147 
148     for(int i=ans.size()-1;i>=0;i--)
149     {
150         if(i!=ans.size()-1) printf("->");
151         cout << ans[i];
152     }
153     puts("");
154     printf("%d %d %d
",Cnt,d[M[ed]],d3[M[ed]]);
155 }

View Code

第二，可以使用从头开始dfs的方法，直接在图G上搜索路径，当到达终点且路径是最短路时，Cnt才加1（似乎这种方法看起来更好）。具体见代码（这样的话p数组也不需要了，只需要pre数组即可）：

  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 = 200 + 5;
 17 
 18 struct edge
 19 {
 20     int v,w;
 21     int kill;
 22 };
 23 vector<edge> G[N];
 24 edge pre[N];
 25 vector<edge> p[N];
 26 int d[N],cnt[N],d2[N],d3[N];
 27 map<string,int> M;
 28 map<int,string> M2;
 29 string st,ed;
 30 
 31 void dij()
 32 {
 33     memset(d,inf,sizeof(d));
 34     memset(d2,0,sizeof(d2));
 35     memset(d3,0,sizeof(d3));
 36     d[1] = 0;
 37     d2[1] = 0;
 38     d3[1] = 0;
 39     priority_queue<pii,vector<pii>,greater<pii> > Q;
 40     Q.push(pii(0,1));
 41     while(!Q.empty())
 42     {
 43         pii x = Q.top();Q.pop();
 44         int u = x.second;
 45         int dis = x.first;
 46         if(d[u] != dis) continue;
 47         for(int i=0;i<G[u].size();i++)
 48         {
 49             edge e = G[u][i];
 50             if(d[e.v] >= d[u]+e.w)
 51             {
 52                 if(d[e.v] > d[u]+e.w)
 53                 {
 54                     d[e.v] = d[u]+e.w;
 55                     d2[e.v] = d2[u]+1;
 56                     d3[e.v] = d3[u]+e.kill;
 57                     Q.push(pii(d[e.v],e.v));
 58                     pre[e.v] = (edge){u};
 59 
 60                     p[e.v].clear();
 61                     p[e.v].push_back((edge){u});
 62                 }
 63                 else
 64                 {
 65                     p[e.v].push_back((edge){u});
 66 
 67                     if(d2[e.v] <= d2[u]+1)
 68                     {
 69                         if(d2[e.v] < d2[u]+1)
 70                         {
 71                             d[e.v] = d[u]+e.w;
 72                             d2[e.v] = d2[u]+1;
 73                             d3[e.v] = d3[u]+e.kill;
 74                             Q.push(pii(d[e.v],e.v));
 75                             pre[e.v] = (edge){u};
 76                         }
 77                         else
 78                         {
 79                             if(d3[e.v] <= d3[u]+e.kill)
 80                             {
 81                                 if(d3[e.v] < d3[u]+e.kill)
 82                                 {
 83                                     d[e.v] = d[u]+e.w;
 84                                     d2[e.v] = d2[u]+1;
 85                                     d3[e.v] = d3[u]+e.kill;
 86                                     Q.push(pii(d[e.v],e.v));
 87                                     pre[e.v] = (edge){u};
 88                                 }
 89                             }
 90                         }
 91                     }
 92                 }
 93             }
 94         }
 95     }
 96 }
 97 
 98 int Cnt=0;
 99 bool vis[N];
100 void dfs(int u,int dis)
101 {
102     if(u==M[ed] && dis==d[M[ed]]) {Cnt++;return;}
103     for(int i=0;i<G[u].size();i++)
104     {
105         edge e = G[u][i];
106         if(!vis[e.v])
107         {
108             vis[e.v]=1;
109             dfs(e.v,dis+e.w);
110             vis[e.v]=0;
111         }
112     }
113 }
114 
115 int main()
116 {
117     int n,k,tot=0;
118     scanf("%d%d",&n,&k);
119     cin >> st >> ed;
120     M[st] = 1;
121     M2[1] = st;
122     cnt[1] = 0;
123     for(int i=2;i<=n;i++)
124     {
125         string s;
126         cin >> s >> cnt[i];
127         M[s] = i;
128         M2[i] = s;
129     }
130     scanf("%d",&k);
131     while(k--)
132     {
133         string u,v;
134         int w;
135         cin >> u >> v >> w;
136         G[M[u]].push_back((edge){M[v],w,cnt[M[v]]});
137         G[M[v]].push_back((edge){M[u],w,cnt[M[u]]});
138     }
139 
140     dij();
141     memset(vis,0,sizeof(vis));
142     dfs(1,0);
143 
144     vector<string> ans;
145     int now = M[ed];
146     while(now != 1)
147     {
148         ans.push_back(M2[now]);
149         now = pre[now].v;
150     }
151     ans.push_back(st);
152 
153     for(int i=ans.size()-1;i>=0;i--)
154     {
155         if(i!=ans.size()-1) printf("->");
156         cout << ans[i];
157     }
158     puts("");
159     printf("%d %d %d
",Cnt,d[M[ed]],d3[M[ed]]);
160 }

View Code

　　现在想想，原来我的dfs乱搞法也只是弄巧成拙才AC的啊= =。

　　下面是上面那个图的数据：

伟大的数据