洛谷P5304 [GXOI/GZOI2019]旅行者

原题链接：洛谷P5304 [GXOI/GZOI2019]旅行者

题解

题意：在一个无向图中指定k个点，求这k个点中两两最短路长度的最小值

算法：dijkstra+合并点+二进制

1.暴力

对于每一个指定点，跑k次dijkstra，暴力比较最小值，复杂度O(N²logM)。

for(int i=1;i<=K;i++){
    dijkstra(spe[i]);
    for(int j=1;j<=K;j++)
        if(j!=i&&dis[spe[j]]<ans)
            ans=dis[spe[j]];
}

完整代码，50opt：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int MAXN = 1e5 + 7, MAXM = 1e6 + 50;
 5 const LL INF = 1e17 + 7;
 6 int head[MAXN], sz, nxt[MAXM], len[MAXM], to[MAXM];
 7 inline void add(int x, int y, LL z) {
 8     nxt[++sz] = head[x];
 9     head[x] = sz;
10     to[sz] = y;
11     len[sz] = z;
12     nxt[++sz] = head[y];
13     head[y] = sz;
14     to[sz] = y;
15     len[sz] = z;
16 }
17 LL dis[MAXN], ans;
18 int spe[MAXN] /*special point*/, is[MAXN] /*is special*/;
19 bool vis[MAXN];
20 inline void dijkstra(int S) {
21     memset(dis, 0x3f, sizeof(dis));
22     memset(vis, 0, sizeof(vis));
23     priority_queue<pair<LL, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
24     pq.push(make_pair(0, S));
25     while (pq.size()) {
26         pair<LL, int> cur = pq.top();
27         pq.pop();
28         int idx = cur.second;
29         LL dist = cur.first;
30         if (vis[idx] || dis[idx] < dist)
31             continue;
32         vis[idx] = 1;
33         for (int i = head[idx]; i; i = nxt[i])
34             if (!vis[to[i]] && dist + len[i] < dis[to[i]]) {
35                 dis[to[i]] = dist + len[i];
36                 pq.push(make_pair(dis[to[i]], to[i]));
37             }
38     }
39 }
40 int Case, N, M, K;
41 int main() {
42     scanf("%d", &Case);
43     while (Case--) {
44         scanf("%d%d%d", &N, &M, &K);
45         sz = 0;
46         memset(head, 0, sizeof(head));
47         for (int i = 1; i <= M; i++) {
48             int ii, jj;
49             LL kk;
50             scanf("%d%d%lld", &ii, &jj, &kk);
51             add(ii, jj, kk);
52         }
53         memset(is, 0, sizeof(is));
54         for (int i = 1; i <= K; i++) {
55             scanf("%d", spe + i);
56             is[spe[i]] = 1;
57         }
58         ans = INF;
59         for (int i = 1; i <= K; i++) {
60             dijkstra(spe[i]);
61             for (int j = 1; j <= K; j++)
62                 if (j != i && dis[spe[j]] < ans)
63                     ans = dis[spe[j]];
64         }
65         printf("%lld
", ans);
66     }
67     return 0;
68 }

View Code

2.Method1：按二进制位将点分组

因为此题只要求指定点中最近的两个点的最短路径长度，故可

将这k个点分成两组，将每一组的点合并，从这两个点出发求最短路，两点的距离即为分在不同组内的最近的点的距离

而我们如果每次指定一个次数i，将编号二进制位中含有2ⁱ的点分进一组，剩下的在另一组，这样我们只需分log_k次，

for(int j=1;j<=K;j++){
    if(j&i)
        add(S,spe[j],0);
    else
        add(spe[j],T,0);
}
dijkstra();
ans=min(ans,dis[T]);

每一对点必然出现在不同组内至少一次，因为编号不重复所以正确性显而易见，每次结果的最小值即为所求

AC代码8622 ms

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int MAXN = 1e5 + 7, MAXM = 1e6 + 50;
 5 const LL INF = 1e17 + 7;
 6 int head[MAXN], sz, nxt[MAXM], len[MAXM], to[MAXM];
 7 inline void add(int x, int y, LL z) {
 8     nxt[++sz] = head[x];
 9     head[x] = sz;
10     to[sz] = y;
11     len[sz] = z;
12 }
13 LL dis[MAXN], ans;
14 int spe[MAXN], S, T;
15 bool vis[MAXN];
16 inline void dijkstra() {
17     memset(dis, 0x3f, sizeof(dis));
18     memset(vis, 0, sizeof(vis));
19     priority_queue<pair<LL, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
20     pq.push(make_pair(0, S));
21     dis[S] = 0;
22     while (pq.size()) {
23         pair<LL, int> cur = pq.top();
24         pq.pop();
25         int idx = cur.second;
26         LL dist = cur.first;
27         if (vis[idx] || dis[idx] < dist)
28             continue;
29         vis[idx] = 1;
30         for (int i = head[idx]; i; i = nxt[i])
31             if (!vis[to[i]] && dist + len[i] < dis[to[i]]) {
32                 dis[to[i]] = dist + len[i];
33                 pq.push(make_pair(dis[to[i]], to[i]));
34             }
35     }
36 }
37 int Case, N, M, K;
38 int tmp[MAXN], sz_;
39 int main() {
40     scanf("%d", &Case);
41     while (Case--) {
42         scanf("%d%d%d", &N, &M, &K);
43         sz = 0;
44         memset(head, 0, sizeof(head));
45         for (int i = 1; i <= M; i++) {
46             int ii, jj;
47             LL kk;
48             scanf("%d%d%lld", &ii, &jj, &kk);
49             add(ii, jj, kk);
50         }
51         for (int i = 1; i <= K; i++) {
52             scanf("%d", spe + i);
53         }
54         ans = INF;
55         memcpy(tmp, head, sizeof(tmp));
56         sz_ = sz;
57         S = N + 1;
58         T = N + 2;
59         for (int i = 1; i <= K; i <<= 1) {
60             memcpy(head, tmp, sizeof(head));
61             sz = sz_;
62             for (int j = 1; j <= K; j++) {
63                 if (j & i)
64                     add(S, spe[j], 0);
65                 else
66                     add(spe[j], T, 0);
67             }
68             dijkstra();
69             ans = min(ans, dis[T]);
70             memcpy(head, tmp, sizeof(head));
71             sz = sz_;
72             for (int j = 1; j <= K; j++) {
73                 if (j & i)
74                     add(spe[j], T, 0);
75                 else
76                     add(S, spe[j], 0);
77             }
78             dijkstra();
79             ans = min(ans, dis[T]);
80         }
81         printf("%lld
", ans);
82     }
83     return 0;
84 }

View Code

3.Method2：玄学优化

还是考虑暴力，加上两个剪枝：

(1)在dijkstra时一旦找到不为起点的指定点，立刻更新ans并退出

(2)在dijkstra时一旦当前距离大于等于ans，立即退出

if(dist>ans)
    return;
if(is[idx]&&idx!=S){
    ans=min(ans,dist);
    return;
}

正确性证明：

(1)因为有优先队列，所以第一个找到的指定点一定是最近的

(2)显而易见，dijkstra找出来的距离是递增的

复杂度：（如果有dalao能严格证明请在评论区@我，谢谢！）

感性理解，通常为O(N*logM*大常数+K*N)（主要是k次memset的复杂度），手打数据估计O(sqrt(K)*N*logM)

考虑极端情况，

①k特别大，图十分密集，则每次dijkstra复杂度特别低，接近于O(1)

②k特别小，图十分稀疏，则每次dijkstra接近O(N*logM)，但随着k的增大急速下降

③k折中，形似菊花图，特殊点集中于菊花瓣上，菊花中心尽可能复杂

想要卡这种暴力非常困难，可以放心使用

AC代码：2251 ms

View Code

二进制分组可以结合玄学优化，不会被卡3328 ms

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int MAXN=1e5+7,MAXM=1e6+50;
 5 const LL INF=1e17+7;
 6 int head[MAXN],sz,nxt[MAXM],len[MAXM],to[MAXM];
 7 inline void add(int x,int y,LL z){
 8     nxt[++sz]=head[x]; head[x]=sz; to[sz]=y; len[sz]=z;
 9 }
10 LL dis[MAXN],ans;
11 int spe[MAXN],S,T;
12 bool vis[MAXN];
13 inline void dijkstra(){
14     memset(dis,0x3f,sizeof(dis));
15     memset(vis,0,sizeof(vis));
16     priority_queue<pair<LL,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
17     pq.push(make_pair(0,S));
18     dis[S]=0;
19     while(pq.size()){
20         pair<LL,int> cur=pq.top();
21         pq.pop();
22         int idx=cur.second;
23         LL dist=cur.first;
24         if(dist>=ans){
25             return;
26         }
27         if(idx==T){
28             ans=dist;
29             return;
30         }
31         if(vis[idx]||dis[idx]<dist)
32             continue;
33         vis[idx]=1;
34         for(int i=head[idx];i;i=nxt[i])
35             if(!vis[to[i]]&&dist+len[i]<dis[to[i]]){
36                 dis[to[i]]=dist+len[i];
37                 pq.push(make_pair(dis[to[i]],to[i]));
38             }
39     }
40 }
41 int Case,N,M,K;
42 int tmp[MAXN],sz_;
43 int main(){
44     scanf("%d",&Case);
45     while(Case--){
46         scanf("%d%d%d",&N,&M,&K);
47         sz=0;
48         memset(head,0,sizeof(head));
49         for(int i=1;i<=M;i++){
50             int ii,jj;
51             LL kk;
52             scanf("%d%d%lld",&ii,&jj,&kk);
53             add(ii,jj,kk);
54         }
55         for(int i=1;i<=K;i++){
56             scanf("%d",spe+i);
57         }
58         ans=INF;
59         memcpy(tmp,head,sizeof(tmp));
60         sz_=sz;
61         S=N+1;
62         T=N+2;
63         for(int i=1;i<=K;i<<=1){
64             memcpy(head,tmp,sizeof(head));
65             sz=sz_;
66             for(int j=1;j<=K;j++){
67                 if(j&i)
68                     add(S,spe[j],0);
69                 else
70                     add(spe[j],T,0);
71             }
72             dijkstra();
73             ans=min(ans,dis[T]);
74             memcpy(head,tmp,sizeof(head));
75             sz=sz_;
76             for(int j=1;j<=K;j++){
77                 if(j&i)
78                     add(spe[j],T,0);
79                 else
80                     add(S,spe[j],0);
81             }
82             dijkstra();
83             ans=min(ans,dis[T]);
84         }
85         printf("%lld
",ans);
86     }
87     return 0;
88 }

View Code