「找性质+比较强的分层图」 [Codeforces 1209F] Koala and Notebook

· · 题解

这题是真的有趣。虽然场上并没有去写（感觉写了也是不可能过的，因为细节比较多）。

一开始觉得「难道不是把出边 xjb 排个序就做完了嘛」。然后发现被叉了，心情郁闷(x

考虑如何比较「编号相连得到的十进制数」的大小，那必然是先比较位数，再从头开始比较权值。于是就有个特别强的建图技巧：拆边。考虑把一条编号为 (\overline{a_1a_2\cdots a_k})_{10} 的边拆成两条有向链，链上的边的边权分别为 a_1,a_2\cdots a_k。

然后考虑进行类似分层图的 BFS。这个分层图的细节很丰富：

0、分层的目的是，控制遍历顺序，使得 BFS 的最优性也在当前问题中体现。即使得对于每个点，最先被遍历时一定是最短路。

1、首先要先忽略边权进行分层。

2、其次考虑如果存在多条出边，必然是走权最小的那条边。

3、只符合上面两条还是不对的。因为考虑如果某个点 t 有两条入边 e_1,e_2 满足 val(e_1)<val(e_2)，他们在 BFS 树上的深度相同，那么如果单纯按点来转移，可能会出现先走 e_2 再走 e_1 的情况，而此时 t 已经被更新完毕就会导致出错。所以还要按照边权从 0 到 9 进行再分层。

可以知道这样做最后复杂度一定不会超过 O(10\times m) 。

int ob ;
int cnt ;
int n, m ;
int arr[M] ;
int f[N] ;
int g[N] ;
int T ;

vector <int> q[N] ;
vector <int> E[N][10] ;

int main(){
    cin >> n >> m ;
    int x, y, z ; cnt = n ;
    for (int i = 1 ; i <= m ; ++ i){
        x = qr(), y = qr() ; ob = 0 ; z = i ;
        while (z) arr[++ ob] = z % 10, z /= 10 ; z = x ;
        for (int j = ob ; j > 1 ; -- j)
            E[x][arr[j]].push_back(++ cnt), x = cnt ;
        E[x][arr[1]].push_back(y) ;
        for (int j = ob ; j > 1 ; -- j)
            E[y][arr[j]].push_back(++ cnt), y = cnt ;
        E[y][arr[1]].push_back(z) ;
    }
    g[1] = T = 1 ;
    q[1].push_back(1) ;
    for (int d = 1 ; d <= T ; ++ d){
//        if (!q[d].size()) break ;
        for (z = 0 ; z < 10 ; ++ z){
            auto t = q[d].begin() ;
            while (t != q[d].end()){
                x = *t ;
                for (auto y : E[x][z]){
                    if (g[y]) continue ;
                    f[y] = (f[x] * 10ll + z) % P ;
                    g[y] = 1, q[T + 1].push_back(y) ;
                }
                ++ t ;
            }
            if (q[T + 1].size()) ++ T ;
        }
    }
    for (int i = 2 ; i <= n ; ++ i)
        printf("%d\n", f[i]) ; return 0 ;
}