给定一个有 n 个节点,m 条边的无向图,每边都涂有1种颜色。求节点1到n的一条路径,使得经过的边数最少,在此前提前,经过边的颜色序列最小。可能有自环和重边。
输入共 m+1 行,第1行包括两个整数:m和n。之后的m行,每行都包含3个整数a、b、c,表示a和b之间有一条颜色为c的路径。
输出共两行,第1行包含正整数k,表示节点1到n至少需要经过k条边。第2行包含k个由空格隔开的正整数,表示节点1到n经过的边的颜色。
4 6
1 2 1
1 3 2
3 4 3
2 3 1
2 4 4
3 1 1
2
1 3
节点1到4至少经过两条边:1 > 3,颜色为1(最后输入的那条边);3 > 4,颜色为3。
本问题求解节点1到n的最短距离,在此前提下,色号序列最小。可以先求最短距离,然后考察色号。因为在从节点1出发的多条边中,并不知道哪条边是最短路径上的边,所以无法确定最小色号。
1 从节点n反向广度优先遍历标高,节点1的高度正好为从节点1到n的最短距离。
2 从节点1正向广度优先遍历,沿着高度减1的方向遍历,找色号小的点,如果多个色号都最小,则考察下一个色号哪个最小,直到节点n结束。
1 根据输入样例创建图,然后节点n反向广度优先遍历标高,节点1的高度为2,即节点1到n的最短距离为2,输出2。
2 从节点1正向广度优先遍历,沿着高度减1的方向遍历,找边商色号小的邻接点,节点1到2的色号为1,节点1到3的色号为1,节点1到3的另外一条道路色号为2,最小色号为1,输出1,。目前无法确定选择哪条边,因此将可能走的两个邻接点2和3入队并暂存。
3 从节点2和节点3出发,沿着高度减1的方向遍历,找边上色号小的邻接点,节点2到4的色为4,节点3到4的色号为3,最小色号为3,输出3。
- package graph.uva1599;
-
- import java.util.LinkedList;
- import java.util.Queue;
- import java.util.Scanner;
-
- public class UVA1599 {
- static final int inf = 0x7fffffff;
- static final int N = 100000 + 5;
- static final int M = 200000 + 5;
- static int n;
- static int m;
- static int cnt;
- static boolean vis[];
- // 保存节点号
- static Queue<Integer> q1 = new LinkedList<>();
- // 保存色号
- static Queue<Integer> q2 = new LinkedList<>();
- // 保存色号最小的边关联的邻接点号
- static Queue<Integer> q3 = new LinkedList<>();
- static int head[];
- static int dis[] = new int[N];
- static Edge e[] = new Edge[M];
-
- static {
- for (int i = 0; i < e.length; i++) {
- e[i] = new Edge();
- }
- }
-
- // 添加一条边
- static void add(int u, int v, int c) {
- e[++cnt].to = v;
- e[cnt].c = c;
- e[cnt].next = head[u];
- head[u] = cnt;
- }
-
- // 逆向标高求最短距离
- static void bfs1() {
- int u, v;
- vis = new boolean[N];
- dis[n] = 0;
- q1.add(n);
- vis[n] = true;
- while (!q1.isEmpty()) {
- u = q1.peek();
- q1.poll();
- vis[u] = true;
- for (int i = head[u]; i > 0; i = e[i].next) {
- v = e[i].to;
- if (vis[v])
- continue;
- dis[v] = dis[u] + 1;
- q1.add(v);
- vis[v] = true;
- }
- }
- }
-
- // 正向求色号序列
- static void bfs2() {
- int u, v, minc, c;
- boolean first = true;
- vis = new boolean[N];
-
- vis[1] = true;
- // 1号结点所有邻接点
- for (int i = head[1]; i > 0; i = e[i].next)
- // 高度减1的邻接点
- if (dis[e[i].to] == dis[1] - 1) {
- q1.add(e[i].to);
- q2.add(e[i].c);
- }
- while (!q1.isEmpty()) {
- minc = inf;
- while (!q1.isEmpty()) {
- v = q1.peek();
- q1.poll();
- c = q2.peek();
- q2.poll();
- if (c < minc) {
- while (!q3.isEmpty()) // 发现更小队列清空
- q3.poll();
- minc = c;
- }
- if (c == minc)
- q3.add(v);
- }
- if (first)
- first = false;
- else
- System.out.print(" ");
- System.out.print(minc);
- while (!q3.isEmpty()) { // 所有等于最小色号的结点
- u = q3.peek();
- q3.poll();
- if (vis[u])
- continue;
- vis[u] = true;
- for (int i = head[u]; i > 0; i = e[i].next) { // 扩展每一个结点
- v = e[i].to;
- if (dis[v] == dis[u] - 1) {
- q1.add(v);
- q2.add(e[i].c);
- }
- }
- }
- }
- }
-
- public static void main(String[] args) {
- Scanner scanner = new Scanner(System.in);
- int u, v, c;
- while (true) {
- n = scanner.nextInt();
- m = scanner.nextInt();
- head = new int[N];
- for (int i = 0; i < head.length; i++) {
- head[i] = 0;
- }
-
- cnt = 0;
- for (int i = 1; i <= m; i++) {
- u = scanner.nextInt();
- v = scanner.nextInt();
- c = scanner.nextInt();
-
-
- add(u, v, c);
- add(v, u, c);
- }
- bfs1();
- System.out.println(dis[1]);
-
- bfs2();
- System.out.println();
- }
- }
- }
-
- class Edge {
- int to;
- int c;
- int next;
- }
绿色为输入,白色为输出。