Ideal Path（UVA - 1599）

author ：Alex_Dawn

Title Description

Given a nn A little bit mm Undirected graph of strip and edge , Each side is painted 1 Color . Find the point 11 point-to-point nn A path for , To minimize the number of sides to pass , Under this premise , The color sequence passing through the edge is the smallest . There may be self rings and double edges . Input ensures that at least one connection exists 11 and nn The path of .

I/o sample

Input

4 6

1 2 1

1 3 2

3 4 3

2 3 1

2 4 4

3 1 1

Output

2

1 3

Ideas

This question has been used twice bfs, From the end bfs Record the shortest distance from each node to the end , From the beginning bfs Record the minimum order of the color dictionary , Data uses adjacency table to store the number of graph storage edges , At the same time, use the array subscript to represent the number of edges

Be careful

about bfs Tags accessed

From the beginning bfs For the first time bfs Result

Pay attention to self ring and double edge problem

AC Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000; //  Maximum number of vertices 
struct Edge { //  edge 
    int u, v, c;
    Edge(int _u, int _v, int _c) : u(_u), v(_v), c(_c) {} //  Default constructor 
};
vector<Edge> edge; //  Edge cache , Array subscript as number 
vector<int> G[maxn]; //  Adjacency table to store graph , The edges are numbered ;
int n, m, a, b, c;
int d[maxn], vis[maxn]; // d: The distance from the end point to each point （ level ）;vis： Access array 
void revBfs() { //  Traverse from the end , Calculate the distance to each point 
    memset(d, 0, sizeof(d)); memset(vis, 0, sizeof(vis)); //  initialization 
    queue<int> q;
    q.push(n-1); vis[n-1] = 1; //  Finish line up 
    while (!q.empty()) {
        int u = q.front(); q.pop(); //  The top team 
        for (int e : G[u]) { //  Each adjacent side 
            int v = (u == edge[e].u) ? edge[e].v : edge[e].u;// similar if Judge  , Ternary expression  
            if (vis[v] == 0) { //  Not accessed 
                d[v] = d[u] + 1; //  distance / Level update 
                q.push(v);
                vis[v] = 1; //  Tag access 
            }
        }
    }
}
void bfs() { //  From the beginning bfs, Record the path with the smallest dictionary order 
    printf("%d\n", d[0]); //  Shortest distance 
    memset(vis, 0, sizeof(vis)); //  initialization 
    vector<int> next{0}, ans;
    for (int i=0; i < d[0]; i ++) { //  Hierarchical traversal 
        int minColor=0x3fffffff; //  Minimum color value , Is an infinite constant  
        for (int u : next) //  The vertex of this layer （ Find out the minimum color value from this layer to the next layer ）
            for (int e : G[u]) { //  All sides 
                int v = (u == edge[e].u) ? edge[e].v : edge[e].u; //  Determine the next vertex 
                if (d[u] == d[v]+1 && edge[e].c < minColor) minColor = edge[e].c; //  Find the smallest color edge that can reach the end   
            }
        ans.push_back(minColor); //  Store the minimum color 
        vector<int> tnext; //  Temporary storage 
        for (int u : next) //  Add the point with the minimum color value from this layer to the next layer to the next round next
            for (int e : G[u]) {
                int v = (u == edge[e].u) ? edge[e].v : edge[e].u;
                if (d[u] == d[v]+1 && vis[v] == 0 && edge[e].c == minColor) {
                    tnext.push_back(v);
                    vis[v] = 1;
                }
            }
        next = tnext; //  to update next Array 
    }
    for (int i=0; i < ans.size(); i ++) printf("%d%s", ans[i], i == ans.size()-1 ? "\n" : " ");
}
int main() {
    while (scanf("%d %d", &n, &m) == 2) {
        edge.clear(); fill(G, G+maxn, vector<int>{}); //  initialization 
        while (m --) {
            scanf("%d %d %d", &a, &b, &c);
            if (a == b) continue; //  Deal with self loop ,continue jump  
            G[a-1].push_back(edge.size()); //  Undirected graph , from 0 Start storage 
            G[b-1].push_back(edge.size());
            edge.push_back({a-1,b-1,c}); //  Edge cache 
        }
        revBfs();
        bfs();
    }
    return 0;
}