题解：P6606 [Code+#7] 最小路径串

· · 题解

我原本以为这道题可能是树形 DP 什么的，一看是黄，突然就感觉没事了。

题意

题目

这道题其实就是给一个图中的每个点赋予一个值，现在问我们怎么样去遍历，使得这个遍历的字典序最小。

思路

算法

显然的，我们应该用 dfs 算法来实现这道题，一方面是这种图的遍历貌似只有深搜能满足，另一方面是深搜好写。

但是我们要注意一下输入方面，这种存图方式类似于邻接矩阵（个人理解），告诉你哪两个点是相通的，图论有问题的推荐去看这篇博客。

然后直接 dfs 爆搜一遍，更新答案就 OK 了。

存储方式

我们来用邻接表来存图，因为在 10^7 面前，如果硬要用邻接矩阵来的话，就会爆内存，所以用邻接表会好一些，再考虑优化一下内存，那么我们就可以用 vector 来存储，这样明显能让我们的内存变小，防止内存不够用，而且我们的 vector 加入一个节点直接 push_back() 就好了，会方便许多，STL 有很多方便我们实现算法的容器。

遍历图真的没什么好讲的，就是遍历每个节点，然后把这个节点对应的边递归下去，把节点都遍历一遍，这样就是我们 dfs 的特点了。

细节

重边和自环就需要让我们注意一个细节，那就是不遍历已经遍历过的节点，建议开一个 state 数组，bool 类型，每次遍历都将这个点设为 true（定义时的初始值是 false），然后就可以排除掉重边和自环了。

然后就是取模，建议用 const 或者 #define，这样不容易出错。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
const int Mod=998244353;//记得取模
typedef long long LL;
//long long还是很重要的
int n,m;
vector<int>g[N];//vector防爆空间
LL ans[N];
void dfs(int u,LL now)//正常的 dfs 遍历图
{
    ans[u]=now;
    for (auto v:g[u])
    {
        if (ans[v]!=-1) continue;
        dfs(v,(now*1000000+v)%Mod);//取模
    }
}
int main(){
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        int x=0,y=0;
        for (int j=1;j<=6;j++)
        {
            char op;
            cin>>op;
            x=x*10+op-48;
        }
        for (int j=1;j<=6;j++)
        {
            char op;
            cin>>op;
            y=y*10+op-48;
        }
        //上面两个 for 是用来记录数字的，不然不好输入
        if (x==y) continue;
        g[x].push_back(y);
        g[y].push_back(x);
        //同上
    }
    memset(ans,-1,sizeof ans);//memset一遍-1主要作用是看这个节点是否遍历过
    for (int i=0;i<=n;i++)
        sort(g[i].begin(),g[i].end());//排序是方便我们对于这个图的遍历
    dfs(0,0);//用 dfs 来实现
    for (int i=1;i<n;i++)
        printf("%lld\n",ans[i]);
    return 0;
}

完结撒花！！！