Ideal path problem

One   Problem description

Given a  n  Nodes ,m  Undirected graph of strip and edge , Painted on each side 1 Color . Find the node 1 To n A path for , To minimize the number of sides to pass , In advance , The color sequence passing through the edge is the smallest . There may be self rings and double edges .

Two   Input and output

1  Input

Input common  m+1  That's ok , The first 1 The row contains two integers ：m and n. After that m That's ok , Each line contains 3 It's an integer a、b、c, Express a and b There's a color line between c The path of .

2  Output

The output consists of two lines , The first 1 The line contains positive integers k, Representation node 1 To n At least you need to go through k side . The first 2 Line inclusion k Positive integers separated by spaces , Representation node 1 To n The color of the edges that pass .

3  sample input

4 6

1 2 1

1 3 2

3 4 3

2 3 1

2 4 4

3 1 1

4  sample output

2

1 3

node 1 To 4 At least two sides ：1 > 3, The color is 1（ The last input side ）;3 > 4, The color is 3.

3、 ... and   analysis

The solution node of this problem 1 To n The shortest distance , Under this premise , The color number sequence is the smallest . You can find the shortest distance first , Then examine the color number . Because in the slave node 1 Of the multiple sides of departure , I don't know which edge is the shortest path , Therefore, the minimum color number cannot be determined .

Four   Algorithm design

1  From the node n Reverse breadth first traverses the elevation , node 1 Is exactly the height of the slave node 1 To n The shortest distance .

2  From the node 1 Forward breadth first traversal , Decrease along the height 1 Direction traversal of , Look for a smaller color number , If multiple color numbers are the smallest , The next color number is the smallest , Up to the node n end .

5、 ... and   Graphic analysis

1  Create a diagram based on the input sample , And then the nodes n Reverse breadth first traverses the elevation , node 1 The height of 2, That is node 1 To n The shortest distance is 2, Output 2.

2  From the node 1 Forward breadth first traversal , Decrease along the height 1 Direction traversal of , Find the adjacency point with small edge quotient number , node 1 To 2 The color number of is 1, node 1 To 3 The color number of is 1, node 1 To 3 The color number of the other road is 2, The minimum color number is 1, Output 1,. It is currently not possible to determine which edge to select , Therefore, it is possible to take two adjacent contacts 2 and 3 Join the team and temporarily store .

3  From the node 2 And nodes 3 set out , Decrease along the height 1 Direction traversal of , Find the adjacency point with small color number on the edge , node 2 To 4 The color of is 4, node 3 To 4 The color number of is 3, The minimum color number is 3, Output 3.

6、 ... and   Code

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[];
    //  Save node number 
    static Queue<Integer> q1 = new LinkedList<>();
    //  Save color number 
    static Queue<Integer> q2 = new LinkedList<>();
    //  Save the adjacency point number associated with the edge with the smallest color number 
    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();
        }
    }

    //  Add an 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;
    }

    //  Reverse the elevation to find the shortest distance 
    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;
            }
        }
    }

    //  Forward color number sequence 
    static void bfs2() {
        int u, v, minc, c;
        boolean first = true;
        vis = new boolean[N];

        vis[1] = true;
        // 1 All adjacency points of node No 
        for (int i = head[1]; i > 0; i = e[i].next)
            //  Height reduction 1 The adjacency point 
            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()) //  Found smaller queue empty 
                        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()) { //  All nodes equal to the minimum color number 
                u = q3.peek();
                q3.poll();
                if (vis[u])
                    continue;
                vis[u] = true;
                for (int i = head[u]; i > 0; i = e[i].next) { //  Expand each node 
                    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;
}

7、 ... and   test

Green is the input , White is the output .