[Leaf] [P5304] 旅行者

p5304-[gxoi/gzoi2019]-旅行者---洛谷">P5304 [GXOI/GZOI2019] 旅行者 - 洛谷

1. 题面梗概

中译中: 给一个有向图，其中有 $k$ 个点是“兴趣点”。求这 $k$ 个兴趣点中，任意两点之间最短路径的最小值。

2. 逻辑推导

这显然是个最短路问题，最简单的想法就是对每个兴趣点跑一遍 $dijkstra$，但是这样复杂度 $O(k \cdot M \log N)$，对于这题 $k,N,M \leq 10^5$ 来说，绝对是超时的。

我们需要考虑降维， $M \log N$ 的最短路开销绝对省不了，从 $k$ 入手，这里有两种思路解决这道题。

2.1 染色法

我们同样是考虑多源最短路，不过是采用 $Dijkstra$，我们从每个兴趣点出发，向周围的点进行染色扩散。

而因为我们只需要找到一组最短的路径，所以在反图上再跑一遍多源 $Dijkstra$，同样染色。

接着我们只需要遍历所有边 $(u, v, w)$，如果 $u$ 和 $v$ 被两个兴趣点所染色，那么我们就发现了一条从兴趣点 $col1[u]$ 经过 $(u,v)$ 到达 $col[v]$ 的路径，其长度为 $dist1[u] + w + dist2[v]$。

2.2 二进制分组

对于 $k$ 个兴趣点，我们枚举二进制里的第 $i$ 位，把二进制第 $i$ 位是 $0$ 的点放在 $A$ ， $1$ 的点放在 $B$ ，然后用两个超级源点 $(S,T)$ 分别连接 $A$ 集合 和 $B$ 集合，对 $(S,T)$ 跑最短路求最小值即可。

原理是，若 $k$ 个点中最近的两个点为 $x$ 和 $y$，那么 $x$ 和 $y$ 一定有一个二进制位不同，那么它们在分组的时候一定被分到了两边，从而一定能被统计到。

不得不说，这真是个天才的想法。（ 当然，我没想到 ）

3. 代码实现

▶

AcCode

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<int, int>;
using PLI = pair<ll, int>;

const int maxn = 1e5 + 50;
const ll inf = 1e18;

vector<PII> adj[maxn];
vector<PII> radj[maxn];
int ks[maxn];
int n, m, k;

ll d1[maxn], d2[maxn];
int c1[maxn], c2[maxn];

void dijkstra( int type )
{
    ll *dist; int *color; vector<PII> *gragh;
    if( type == 0 ) dist = d1, color = c1, gragh = adj;
    else dist = d2, color = c2, gragh = radj;

    for( int i = 1; i <= n; ++ i )
    {
        dist[i] = inf;
        color[i] = 0;
    } 

    priority_queue< PLI, vector<PLI>, greater<PLI> > pq;
    for( int i = 1; i <= k; ++ i )
    {
        int k = ks[i];
        dist[k] = 0;
        color[k] = k;
        pq.push({ 0, k });
    }

    while( !pq.empty( ) )
    {
        auto [d, u] = pq.top( );
        pq.pop( );
        if( d > dist[u] ) continue;

        for( auto [v, w] : gragh[u] )
        {
            if( dist[u] + w < dist[v] )
            {
                dist[v] = dist[u] + w;
                color[v] = color[u];
                pq.push({ dist[v], v });
            }
        }
    }

}

void solve( )
{
    cin >> n >> m >> k;

    for( int i = 1; i <= n; ++ i )
    {
        adj[i].clear( );
        radj[i].clear( );
    }

    for( int i = 1; i <= m; ++ i )
    {
        int u, v, w;
        cin >> u >> v >> w;
        if( u != v )
        {
            adj[u].push_back({ v, w });
            radj[v].push_back({ u, w });
        }
    }

    for( int i = 1; i <= k; ++ i )
    {
        cin >> ks[i];
    }

    dijkstra( 0 );
    dijkstra( 1 );

    ll ans = inf;

    for( int u = 1; u <= n; ++ u )
    {
        for( auto& [v, w] : adj[u] )
        {
            if( c1[u] && c2[u] && c1[u] != c2[v] )
                ans = min( ans, d1[u] + w + d2[v] );
        }
    }

    cout << ans << '\n';
}

int main( )
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _t;
    cin >> _t;
    while( _t -- )
    {
        solve( );
    }
    return 0;
}

4. 复盘

• 复杂度分析：$O( T \cdot M \log N )$。

• 碎碎念：这是道一题多解的好题，两种思路都很有趣，都可以掌握。

• 关联笔记：最短路体系