题解：P11892 [XRCOI Round 1] C. 草萤有耀终非火

zsj0228 · 2025-11-06 14:50:09 · 题解

题面解释

标记以矩形样方式传递，从给定的若干初始标记点中选最少的点使 (1, 1) 与 (1, m) 被标记。

思路

将网格的行和列抽象为节点，将被标记节点的行和列对应两节点之间连边，则显然一个节点最终被标记的最少初始点即为对应行和列的最短路。故答案转化为第 1 列，第 m 列，第 1 行这 3 点连通的最小代价，枚举中间节点与这 3 点的最短路之和求最小值即可。

code

#include <bits/stdc++.h>

using namespace std;

const int N = 2e4 + 10;
const int M = 2e5 + 10;
const int inf = 7e8;

int n, m, k;
int h[N], to[M << 1], nxt[M << 1], tot;

void add(int u, int v)
{
    to[ ++ tot] = v, nxt[tot] = h[u], h[u] = tot;
    return;
}

int dis[N][3], q[N], l, r;

inline void bfs(int id, int s)
{
    for (int i = 1; i <= n + m; ++ i) dis[i][id] = inf;
    dis[s][id] = 0;
    l = 1, r = 0;
    q[ ++ r] = s;
    while (l <= r)
    {
        int u = q[l ++ ];
        for (int i = h[u], v; i; i = nxt[i])
        {
            v = to[i];
            if (dis[v][id] == inf)
            {
                dis[v][id] = dis[u][id] + 1;
                q[ ++ r] = v;
            }
        }
    }
    return;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d%d%d", &n, &m, &k);
        tot = 0;
        for (int i = 1; i <= n + m; ++ i) h[i] = 0;
        for (int i = 1, u, v; i <= k; ++ i)
        {
            scanf("%d%d", &u, &v);
            add(u, n + v), add(n + v, u);
        }
        bfs(0, 1), bfs(1, n + 1), bfs(2, m + n);
        int res = inf;
        for (int i = 1; i <= n + m; ++ i) res = min(res, dis[i][0] + dis[i][1] + dis[i][2]);
        if (res >= inf) printf("-1\n");
        else printf("%d\n", res);
    }
    return 0;
}