题意分析

我们需要在迷宫中找到从$1$号房间到$n$号房间的最短路径（边数最少），如果有多条最短路径，则选择颜色序列字典序最小的路径。通道是双向的，且可能存在多条通道或自环。

解题思路

1. 广度优先搜索（BFS）：由于边权相同（或视为无权图），BFS可以高效地找到最短路径。
2. 字典序最小路径：在BFS过程中，维护从起点到每个节点的最短路径及其颜色序列的字典序最小值。
3. 分层处理：按距离分层的BFS，确保先处理距离起点更近的节点。
4. 颜色序列比较：对于同一层的节点，优先选择颜色序列字典序较小的路径。

C++代码

#include <iostream>
#include <fstream>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <cstring>

using namespace std;

const int INF = INT_MAX;

typedef pair<int, int> pii;

typedef struct edge
{
    int t;
    int e;
    edge* next;
} edge;
 
typedef struct  node
{
    int t;
    node* next;
} node;

node pool[400000];
bool vis[110000];
node* link[110000];
edge g[1000000];
edge* head[110000];
int cnt;
int q[110000];

int N, M;
int d[110000];
int ans[110000];

inline void add_edge(int s, int t, int e)
{
    g[cnt].t = t;
    g[cnt].e = e;
    g[cnt].next = head[s];
    head[s] = &g[cnt++];

    g[cnt].t = s;
    g[cnt].e = e;
    g[cnt].next = head[t];
    head[t] = &g[cnt++];
}
inline void add_link(int s, int t)
{
    pool[cnt].t = t;
    pool[cnt].next = link[s];
    link[s] = &pool[cnt++];
}

void build()
{

    int s, t, e;
    for(int i = 0; i < M; i++)
    {
        scanf("%d %d %d", &s, &t, &e);
        add_edge(s, t, e);
    }
}
void buildLink()
{
    cnt = 0;
    for(int i = 1; i <= N; i++)
    add_link(d[1] - d[i], i);

}

int main()
{


    scanf("%d %d", &N, &M);
    build();
    memset(d, -1, sizeof(d));

    int s = 0, t = 0;;
    d[N] = 0;
    q[t++] = N;
 
    while(s < t)
    {
        int u = q[s++];

        for(edge* p = head[u]; p; p = p->next)
        {
            if(-1 == d[p->t])
            {
                d[p->t] = d[u] + 1;
                q[t++] = p->t;
            }
        }
    }
    printf("%d\n", d[1]);
    vis[1] = true;
    buildLink();
 
    for(int i = 0; i < d[1]; i++)
    {
        int ans = INF;
        for(node* p = link[i]; p; p = p->next)
        {
            if(vis[p->t])
            {
                int x = p->t;
                for(edge* tp = head[x]; tp; tp = tp->next)
                {
                    if(d[x] - 1 == d[tp->t])
                        ans = min(ans, tp->e);
                }
            }
        }
        if(i)
            putchar(' ');
        printf("%d", ans);
        if(i == d[1] - 1)
        break;

        for(node* p = link[i]; p; p = p->next)
        {
            if(vis[p->t])
            {
                int x = p->t;
                for(edge* tp = head[x]; tp; tp = tp->next)
                {
                    if(ans == tp->e && d[x] - 1 == d[tp->t])
                    {
                        vis[tp->t] = true;
                    }
                }
            }
        }
    }
 
    puts("");

    return 0;
}