CF1209F Koala and Notebook

传送门

思路

一道妙妙题。

我们考虑将一条边拆成若干个点连接的链，这条链上每条边的权值都是一位数。

这样每个点一定是先尽量少经过边，这很 bfs。

对于转移，显然是选权值小的边先走。

但这可能出现一个问题，如果我要更新 \(u\)，有一个 \(v_1\) 指向 \(u\) 边权为 \(x\)，有一个 \(v_2\) 指向 \(u\) 边权为 \(y\)，且 \(v_1\) 在队列中排在 \(v_2\) 前面，但如果 \(v_1\) 与 \(v_2\) 的答案相同， 却有 \(x > y\)，这时显然不优。

因此我们将答案相同的点放在一起，每次先选最小的边进行转移，保证答案的正确性。

代码

#include<bits/stdc++.h>
#define LL long long
#define max(x...) std::max({x})
#define min(x...) std::min({x})
#define FOR(i, x, y) for(int i = (x); i <= (y); i++)
#define ROF(i, x, y) for(int i = (x); i >= (y); i--)
inline int rd()
{
    int sign = 1, re = 0; char c = getchar();
    while(!isdigit(c)){if(c == '-') sign = -1; c = getchar();}
    while(isdigit(c)){re = re * 10 + (c - '0'); c = getchar();}
    return sign * re;
}
namespace MOD
{
    const int mod = 1e9 + 7;
    inline int add(int a, int b) {return a + b >= mod ? a + b - mod : a + b;}
    inline int mul(int a, int b) {return 1ll * a * b % mod;}
    inline int sub(int a, int b) {return a - b < 0 ? a - b + mod : a - b;}
} using namespace MOD;
int n, m, ans[1000005], tot;
std::vector<int> e[1000005][10];
std::queue<std::vector<int>> q;
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    tot = n = rd(), m = rd();
    FOR(i, 1, m)
    {
        int u = rd(), v = rd();
        int bit[10], cnt = 0, h = i;
        while(h) bit[++cnt] = h % 10, h /= 10;
        std::reverse(bit + 1, bit + 1 + cnt);
        if(cnt == 1) {e[u][bit[1]].emplace_back(v), e[v][bit[1]].emplace_back(u); continue;}
        
        e[u][bit[1]].emplace_back(tot + 1);
        FOR(j, 1, cnt - 2)
            e[tot + j][bit[j + 1]].emplace_back(tot + j + 1);
        e[tot + cnt - 1][bit[cnt]].emplace_back(v);

        e[v][bit[1]].emplace_back(tot + cnt - 1);
        FOR(j, 1, cnt - 2)
            e[tot + cnt - j][bit[j + 1]].emplace_back(tot + cnt - j - 1);
        e[tot + 1][bit[cnt]].emplace_back(u);

        tot += cnt - 1;
    }
    FOR(i, 2, tot) ans[i] = -1;
    q.push({1});
    while(!q.empty())
    {
        auto now = q.front(); q.pop();
        FOR(num, 0, 9)
        {
            std::vector<int> in;
            for(int i : now) for(int j : e[i][num])
                if(ans[j] == -1)
                {
                    ans[j] = add(mul(ans[i], 10), num);
                    in.emplace_back(j);
                }
            if(!in.empty()) q.push(in);
        }
    }
    FOR(i, 2, n) printf("%d\n", ans[i]);
    return 0;
}