一、题意
给一个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”,这样就能实现一些比较复杂的最短路径问题。
- 写代码时,增加时间复杂度系数的写法问题不大的,就像这里代码中先通过一次二重循环找最小颜色,再重复一次把最小颜色的边收集起来,这和写成一个循环时间是差不多的,因此应该怎么方便怎么来。。