Moving to the Capital

题目来源：Codeforces Round #693 G

题目链接：https://codeforces.com/contest/1472/problem/G

题目大意

\(n\) 个城市，\(m\) 条单向路径，长度都为 \(1\) 。\(d_i\)表示从首都 \(1\) 到城市i的最短距离。然后就是说从城市 \(i\) 到 \(j\) 有两种行为，第一种随便用，第二种最多只能用一次。我们要求的是从每个城市出发，最终能距首都的最短距离。

解题思路

用\(f\)表示最终结果，\(f[i]\) 的初值等于 \(d[i]\)。我们按 \(d\) 从大到小枚举城市 \(u\)，\(u\) 可以到达城市 \(v\)。

那么如果 \(d[u] < d[v]\)，则 \(u\) 可以直接采用行为 \(1\) 到达 \(v\)，因为是按 \(d\) 从大到小枚举，所以此时 \(f[v]\) 是已知的，则可得 \(f[u] = min(f[u], f[v])\)。

如果 \(d[u] >= d[v]\)，那么 \(u\) 只能采取行为 \(2\) 到 \(v\)，因为已经用过行为 \(2\)，所以 \(v\) 之后只能用 \(1\) 了，即只能往 \(d\) 增大的城市走，所以 \(d[v]\) 是最小值，可得 \(f[u] = min(f[u], d[v])\)。

Code

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

#define MAXN 200005


int d[MAXN], f[MAXN];
bool vis[MAXN];
vector<int> edges[MAXN], c[MAXN];

int main(void)
{
    int T; scanf("%d", &T);
    while(T--) {
        int n, m; scanf("%d%d", &n, &m);
        for(int i=0;i<=n;++i) edges[i].clear(), c[i].clear();
        for(int i=0;i<m;++i) {
            int u, v; scanf("%d%d", &u, &v);
            edges[u].push_back(v);
        }
        // 求d
        memset(vis, false, (n+1) * sizeof(bool));
        queue<int> Q;
        d[1] = 0; vis[1] = true;
        Q.push(1);
        while(Q.size()) {
            int u = Q.front(); Q.pop();
            c[d[u]].push_back(u);           // 与1距离相同的点放一起
            int len = edges[u].size();
            for(int i=0;i<len;++i) {
                int v = edges[u][i];
                if(vis[v]) continue;
                d[v] = d[u] + 1;
                vis[v] = true;
                Q.push(v);
            }
        }
        // 求结果f
        for(int i=1;i<=n;++i) f[i] = d[i];  // f初值等于d
        for(int l=n-1;l>0;--l) {            // 由远到近遍历每一点
            int num = c[l].size();
            for(int i=0;i<num;++i) {
                int u = c[l][i];
                int len = edges[u].size();
                for(int j=0;j<len;++j) {
                    int v = edges[u][j];
                    if(d[u] < d[v]) f[u] = min(f[u], f[v]);
                    else f[u] = min(f[u], d[v]);
                }
            }
        }
        for(int i=1;i<=n;++i) printf("%d ", f[i]);
        printf("\n");
    }
    return 0;
}