题目描述

n 个点 m 条边的无向图中，所有点用从 0 开始的 6 位数字串编号，即 000000、000001、000002、……直到 \(n?1\) 对应的 6 位数字串。保证 \(n≤1e6\)，所以 6 位的编号不会溢出。

对于除了 000000 以外的每个点，你需要找到一条从 000000 出发且不经过重复点的路径，使得路径上所有点的数字串顺次连接形成的串的字典序最小。

比较两个不同的串的字典序的方法是：如果其中某个串是另一个的前缀，则较短的串字典序较小；否则，找出两个串从左往右扫描时遇到的首个不相等的位置，在这个位置上的数字较小的串字典序较小。

由于输出路径过于麻烦，你不需要完整地输出路径，只需要将路径上所有点的数字串视作一个整数，输出这个数对 998244353 取模的结果。

输入格式

从标准输入读入数据。

第一行输入两个整数 \(n\) 和 \(m\)。

第二行输入一个长度为 \(12m\) 的数字串，依次表示每条边。每条边用 12 个数字表示，其中前 6 个与后 6 个数字分别表示这条边所连接的两个点的编号。

注意，输入中可能会包含自环或重边。

输出格式

输出到标准输出。

输出 n?1 行，依次输出除了点 000000 本身以外，点 000000 到每个点的字典序最小的路径，视为整数后对 998244353 取模的结果。

如果点 000000 不可到达某个点，则在对应的行改为输出 -1。

样例1输入

5 5
000000000003000001000003000001000002000002000000000002000003

样例1输出

2000001
2
517560944
-1

样例1解释

从 000000 到 000001 所求的路径对应的串为 000000000002000001。
从 000000 到 000002 所求的路径对应的串为 000000000002。
从 000000 到 000003 所求的路径对应的串为 000000000002000001000003，对 998244353 取模后为 517560944。
从 000000 到 000004 不存在路径。

子任务

子任务1（11分）
\(1≤n≤1e6,m=0\)。

子任务2（55分）

\(1≤n≤10,0≤m≤20\)。

子任务3（34分）

\(1≤n≤1e6,0≤m≤1e6\)。

刚开始拿到这道题的时候还有点晕，首先我们可以否定直接吧路径字符串存下来，我们可以把字符串转化成数来存储。但是我们就无法比较两条路径的字典序先后，但我们又可以发现，一条路径最优，当且仅当它的每一个路径上的数都是最小，但不一定是最短，则我们有以下dfs代码：

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxs=1e7+2e6+100,maxn=1e6+50;
typedef long long ll;
const ll mod=998244353;
vector<int> e[maxn];
int n,m;
char s[maxs];
ll ans[maxn];

inline bool cmp(const int &a,const int &b) {return a<b;}

void dfs(int u,ll dis)
{
    ans[u]=dis;
    int siz=e[u].size();
    for(int i=0;i<siz;i++)
        if(ans[e[u][i]]==-1) dfs(e[u][i],(dis*1000000+e[u][i])%mod);
}

int main()
{
    int u,v;
    scanf("%d%d%s",&n,&m,s);
    memset(ans,-1,sizeof(ans));
    for(int i=1;i<=m;i++)
    {
        u=v=0;
        for(int j=(i-1)*12;j<i*12-6;j++)
            u=(u<<1)+(u<<3)+(s[j]^48);
        for(int j=i*12-6;j<i*12;j++)
            v=(v<<1)+(v<<3)+(s[j]^48);
        if(u==v) continue;
        e[u].push_back(v);e[v].push_back(u);
    }
    for(int i=0;i<n;i++) sort(e[i].begin(),e[i].end(),cmp);
    dfs(0,0);
    for(int i=1;i<n;i++) printf("%lld\n",ans[i]);
    return 0;
}

第七届Code+程序设计全国挑战赛 normal T1 最小路径串

原文：https://www.cnblogs.com/gxm123/p/12943753.html