一、题意

给一个n个点m条边（2<=n<=100000, 1<=m<=200000）的无向图，每条边都涂有一种颜色。求从结点1到结点n的一条最短路径。在此前提下，使得经过边的颜色序列的字典序最小。打印出路径长度和颜色序列。

二、解析

最短路问题的考虑bfs。但是这道题目要打印出最短路径，如果用平常的父节点p数组的方法，没有办法保证按照颜色字典序。因此要考虑其他方法。
这里的方法是使用两次bfs。
第一次是从终点开始的逆向bfs，可以得到所有顶点到终点的距离数组rev_d[maxn]；然后再进行正向bfs，正向bfs时就要沿着rev_d逐一递减的方向遍历，然后在每一步选择颜色最小的方向（可能有多个）。

三、代码

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
const int maxn = 100000 + 5, INF = 1 << 30;
struct edge {
    int to, c;
    edge(int to, int c) : to(to), c(c) {}
};
vector<edge> G[maxn];
int n, m, rev_d[maxn], vis[maxn];

void rev_bfs() {
    fill(vis, vis + n + 1, 0);
    fill(rev_d, rev_d + n + 1, 0);
    queue<int> que;
    que.push(n), vis[n] = 1, rev_d[n] = 0;
    while(!que.empty()) {
        int u = que.front();
        que.pop();
        for(const edge& e : G[u]) if(!vis[e.to]) {
            que.push(e.to), vis[e.to] = 1, rev_d[e.to] = rev_d[u] + 1;
        }
    }
}

void bfs() {
    fill(vis, vis + n + 1, 0);
    vector<int> cur, ans;
    cur.push_back(1), vis[1] = 1;
    for(int i = 0; i < rev_d[1]; i ++) {
        vector<int> tmp;
        int min_c = INF;

        for(int u : cur) {
            for(const edge & e : G[u]) if(rev_d[e.to] == rev_d[u] - 1){
                min_c = min(min_c, e.c);
            }
        }

        for(int u : cur) {
            for(const edge & e : G[u]) if(!vis[e.to] && rev_d[e.to] == rev_d[u] - 1 && e.c == min_c){
                tmp.push_back(e.to);
                vis[e.to] = 1;
            }
        }
        cur = tmp;
        ans.push_back(min_c);
    }
    cout << rev_d[1] << endl;
    for(int i = 0; i < ans.size(); i ++) {
        if(i) cout << " ";
        cout << ans[i];
    }
    cout << endl;
}

int main() {
    while(cin >> n >> m) {
        for(int i = 1; i <= n; i ++) G[i].clear();
        while(m --) {
            int u, v, c;
            cin >> u >> v >> c;
            G[u].push_back(edge(v, c));
            G[v].push_back(edge(u, c));
        }
        rev_bfs();
        bfs();
    }
}

四、归纳

  • 主要是学习了第二种bfs方法：先通过逆向bfs求出距离d[maxn]，然后再进行正向的“bfs”，这样就能实现一些比较复杂的最短路径问题。
  • 写代码时，增加时间复杂度系数的写法问题不大的，就像这里代码中先通过一次二重循环找最小颜色，再重复一次把最小颜色的边收集起来，这和写成一个循环时间是差不多的，因此应该怎么方便怎么来。。