1599 - Ideal Path

之所以不能直接从起点来一次BFS，是因为这样不能保证找到的最短路径的字典序也是最小的。也不能在每次搜索的时候只把连接边权值最短的邻接点加进去，这样可能会根本找不到终点。所以需要两次BFS。

要注意
BFS中，要在某结点被加入进队列之后就把该结点置为已访问。
如果在出队时将该结点置为已访问，就可能把已经在队列里的邻接点又加入队列，导致超时。

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int maxn = 100000 + 10;
const int INF = 1e9 + 10;

// 因为两个结点之间可能不止一条边，因此就不能以普通的邻接矩阵来存储图
// 使用vector将所有结点的邻接点和相应的连接边存起来，下标是一一对应的
vector<int> adj_room[maxn];
vector<int> color[maxn];

int n, m;

// d数组保存每个结点到终点的距离
// ans数组保存最短路径上的每条边的权值
int visited[maxn], d[maxn], ans[maxn];

// 第一遍BFS，从终点开始到起点结束
// 为每个点标记它离终点的距离
// 这样就能够保证从起点开始再来一次BFS时
// 所选择的点都是处在最短路径上的
void bfs1() {
    queue<int> q;
    q.push(n);
    d[n] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (u == 1) return;
        int len = adj_room[u].size();
        for (int i = 0; i < len; i++) {
            int v = adj_room[u][i];
            if (d[v] < 0) {
                // 当前点的所有邻接点，到终点的距离都要+1
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
}

// 第二遍BFS，从起点开始

// ***要注意***
// BFS中，要在某结点被加入进队列之后就把该结点置为已访问
// 如果在出队时将该结点置为已访问，就可能把已经在队列里的邻接点又加入队列，导致超时
void bfs2() {
    queue<int> q;
    q.push(1);
    visited[1] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (u == n) return;
        int len = color[u].size();
        int min_c = INF;
        // 对于当前扩展到的每个结点(即出队结点)
        // 遍历其邻接点，且邻接点需比当前点离终点的距离小1，以确保它在最短路径上
        // 找出连接边权值的最小值
        for (int i = 0; i < len; i++) {
            int v = adj_room[u][i];
            int c = color[u][i];
            if (d[v] == d[u] - 1) {
                if (c < min_c) {
                    min_c = c;
                }
            }
        }
        // step即为保存最短边权值序列的数组的索引
        int step = d[1] - d[u];
        // 如果没设置值，自然要设置成找到的最小权值
        if (!ans[step]) {
            ans[step] = min_c;
        }
        // 如果这一轮新找到的最小值比上一轮找到的还小，就更新
        // 因为每一轮只搜索一个点的邻域，最小边权值可能要几轮才找得到
        else {
            if (min_c < ans[step])
                ans[step] = min_c;
        }
        // 将当前点所有满足三个条件的邻接点加入队列
        // 条件为：未被访问过，离终点距离小1，连接边权值等于上面找到的最小值
        for (int i = 0; i < len; i++) {
            int v = adj_room[u][i];
            int c = color[u][i];
            if (d[v] == d[u] - 1 && !visited[v] && c == min_c) {
                q.push(v);
                visited[v] = 1;
            }
        }
    }
}

int main() {
    while (cin >> n >> m) {
        memset(visited, 0, sizeof(visited));
        memset(d, -1, sizeof(d));
        memset(ans, 0, sizeof(ans));
        for (int i = 0; i < n + 5; i++) {
            adj_room[i].clear();
            color[i].clear();
        }
        int a, b, c;
        for (int i = 0; i < m; i++) {
            cin >> a >> b >> c;
            if (a == b) continue;
            adj_room[a].push_back(b);
            adj_room[b].push_back(a);
            color[a].push_back(c);
            color[b].push_back(c);
        }
        
        bfs1();
        bfs2();
        cout << d[1] << endl;
        cout << ans[0];
        for (int i = 1; i < d[1]; i++) {
            cout << ' ' << ans[i];
        }
        cout << endl;
    }
    return 0;
}