这道题目其实是一道搜索题目，但需要注意，所要查找的答案并不是要最小而是满足路径上所有点的数字串顺次连接形成的串的字典序最小。
因此我们便可以从一个点开始，找到连接该点的最小数字串。举个例子：
$
000001
\begin{cases}
000002\begin{cases}
000008\\
000007
\end{cases}\\
000003\\
000006
\begin{cases}
000004\\
000005
\end{cases}
\end{cases}
$
我们所得的最佳路径为 000001-000002-000007。用 vector 来储存边的值，存储完后将它进行从小到大排序，然后再进行搜索，每次找到相邻边的第一个未更新过的点，然后将其记录在答案之中。(为什么是第一个呢？因为在之前已排过序，所以第一个未更新的点一定是当前答案的最优解！)
最后就是如何记录答案，我们用 ans[i] 储存 $0$ 至 $i$ 的最优解，然后搜索得到的新点可以用 (nowans * 1000000 + next) % mod 记录，再举一个例子：
$000002 ->000005$ 就是 $ 2 \times 10^6 + 5$。
注意：这相当于一张无向图，且包含了重边与自环。因此在处理的时候要注意这类特殊的情况。
最后是代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define INF 0x3f3f3f3f
#define MOD 998244353
#define ll long long
#define MAX 2000005
using namespace std;
vector <ll> e[MAX];
ll ans[MAX];
bool cmp(int x,int y) {return x < y;}
void dfs(int st,ll s);
int main()
{
int n,m;
cin>>n>>m;
memset(ans,-1,sizeof(ans));
for(int i = 1;i <= m;++i)
{
int a = 0,b = 0;char x;
for(int j = 1;j <= 6;++j) cin>>x,a = a * 10 + x - '0';
for(int j = 1;j <= 6;++j) cin>>x,b = b * 10 + x - '0';
if(a != b)
e[a].push_back(b),e[b].push_back(a);
}
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) cout<<ans[i]<<endl;
return 0;
}
void dfs(int st,ll s)
{
ans[st] = s;
for(int i = 0;i < e[st].size();++i)
if(ans[e[st][i]] == -1)
dfs(e[st][i],(s * 1000000 + e[st][i]) % MOD);
}
|
