理想路径问题

一 问题描述

给定一个有 n 个节点，m 条边的无向图，每边都涂有1种颜色。求节点1到n的一条路径，使得经过的边数最少，在此前提前，经过边的颜色序列最小。可能有自环和重边。

二 输入和输出

1 输入

输入共 m+1 行，第1行包括两个整数：m和n。之后的m行，每行都包含3个整数a、b、c，表示a和b之间有一条颜色为c的路径。

2 输出

输出共两行，第1行包含正整数k，表示节点1到n至少需要经过k条边。第2行包含k个由空格隔开的正整数，表示节点1到n经过的边的颜色。

3 输入样例

4 6

1 2 1

1 3 2

3 4 3

2 3 1

2 4 4

3 1 1

4 输出样例

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;
}

七 测试

绿色为输入，白色为输出。