【双向bfs（一次可也）】【非简单图的最短路】UVa1599 Ideal Path 【紫书6-20经典例题】【无向图求字典序最小的最短路】

程序员文章站 2022-03-12 09:51:02

...

【双向bfs（一次也可）】【非简单图的最短路】UVa1599 Ideal Path 【紫书6-20经典例题】【无向图求字典序最小的最短路】

New labyrinth attraction is open in New Lostland amusement park. The labyrinth consists of n rooms connected by m passages. Each passage is colored into some color ci. Visitors of the labyrinth are dropped from the helicopter to the room number 1 and their goal is to get to the labyrinth exit located in the room number n.

Labyrinth owners are planning to run a contest tomorrow. Several runners will be dropped to the room number 1. They will run to the room number n writing down colors of passages as they run through them. The contestant with the shortest sequence of colors is the winner of the contest. If there are several contestants with the same sequence length, the one with the ideal path is the winner. The path is the ideal path if its color sequence is the lexicographically smallest among shortest paths.

Andrew is preparing for the contest. He took a helicopter tour above New Lostland and made a picture of the labyrinth. Your task is to help him find the ideal path from the room number 1 to the room number n that would allow him to win the contest.

Note:

A sequence (a1, a2,…, ak) is lexicographically smaller than a sequence (b1, b2,…, bk) if there exists isuch that ai < bi, and aj = bj for all j < i.

Input

The input file contains several test cases, each of them as described below.

The first line of the input file contains integers n and m – the number of rooms and passages, respectively(2 $\leq$ n $\leq$ 100000, 1 $\leq$ m $\leq$ 200000). The following m lines describe passages, each passage is described with three integer numbers: ai, bi, and ci – the numbers of rooms it connects and its color (1 $\leq$ ai, bi $\leq$ n, 1 $\leq$ ci $\leq$ 109). Each passage can be passed in either direction. Two rooms can be connected with more than one passage, there can be a passage from a room to itself. It is guaranteed that it is possible to reach the room numbern from the room number 1.

Output

For each test case, the output must follow the description below.

The first line of the output file must contain k – the length of the shortest path from the room number 1 to the room number n. The second line must contain k numbers – the colors of passages in the order they must be passed in the ideal path.

Sample Input

4 6
1 2 1
1 3 2
3 4 3
2 3 1
2 4 4
3 1 1

Sample Output

2
1 3

题意：
有n个点，m条路，每一条路都涂有颜色，要从1到n，求最短路，如果有多条，那么选取颜色字典序最小的路，注意一条路可能连接两个相同的点，一对点之间可能有多条路径。保证一定有解。

TIPS：

结论：无需保存父节点也能得到最短路，方法是从终点开始倒着走bfs，得到每个节点i到终点的最短距离d[i]，然后直接从起点开始走A，但是每一次到一个新的节点B时，要保证dep[B] = dep[A] - 1，这样走过的路一定是一条最短路。

方法一：双向BFS

思路：

先从终点开始走bfs，得到每一个点到终点的距离。【相当于得到一个层次图】
然后从起点开始走bfs，按照上述Tips走，每次找距离减一的点走【即找下一层次的点】，选择字典序最小的入队，如果有多个最小颜色，将他们都入队，并将每一层次的最小颜色记录在数组中，数组的下标用层次深度记录【层次深度为d[1] - d[i]】。走下一步时，需要考虑从这些点出发的所有点。

注意：

由于有自环和重边的存在，因此满足条件的一个点可能多次被加到队列，这样的复杂度将会成指数级。所以应该加一个vis数组进行标记。【一定要注意细节，否则很容易TLE】
第一次bfs终止时机：第一次找到起点就终止，你也许会疑惑这样是否能够找到所有的最短路，其实是可以的，因为bfs是一层层推进的，比如最短路长为5，也就是说第五步走到起点，那么在走第5层次之前，已经将所有深度为4的点走过了，那么起点5一定是由这些4点走来的，那么我们只需要从5起点往前找4点，看是哪个4点走到它的，如果有多条最短路，那么就有这么多个能够走到5点的4点。
第二次bfs终止时机：将终点从队列里取出时才终止，这样才能遍历完所有导向终点且路径长度一致的边，因为把终点取出来说明最后一层次都了，要找从终点再往后走了，说明到终点的所有边都遍历过一遍了，这样的结果才正确。如果一遇到终点，还没有把它放进去队列前就终止，这样只是有一条边走向终点就结束了，并没有考虑所有最短路。

AC代码：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f

using namespace std;

const int maxn = 100005;
vector<int> g[maxn], w[maxn];
int n, m, vis[maxn], d[maxn], ans[maxn];

void bfs()
{
    memset(d, INF, sizeof(d));
    queue<int> q;
    q.push(n);
    d[n] = 1;
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        int len = g[cur].size();
        for(int i = 0; i < len; i++)
        {
            int t = g[cur][i];
            if(t == 1)
            {
                d[t] = d[cur] + 1;
                printf("%d\n", d[t] - 1);
                return ;
            }
            else if(d[t] > d[cur] + 1)
            {
                d[t] = d[cur] + 1;
                q.push(t);
            }
        }
    }
}

void bfs2()
{
    memset(vis, 0, sizeof(vis));
    memset(ans, INF, sizeof(ans));
    queue<int> q;
    q.push(1);
    vis[1] = 1;
    while(!q.empty())
    {
        int minw = INF;//记录从低层次到高其一层次的最小颜色
        int cur = q.front();
        q.pop();
        if(d[cur] == 1)
            return ;
        int len = g[cur].size();
        for(int i = 0; i < len; i++)//从某点出发找所有边
        {
            int t = g[cur][i];
            if(d[t] == d[cur] - 1)//如果深度相差1就说明是最短路上的
                minw = min(minw, w[cur][i]);//记录最小颜色
        }
        for(int i = 0; i < len; i++)//遍历所有导向的点
        {
            int t = g[cur][i];
            if(d[t] == d[cur] - 1 && w[cur][i] == minw && !vis[t])//把所有在最短路上，具有最小颜色边，且没入队的点入队
            {
                q.push(t);
                vis[t] = 1;
            }
        }
        int cc = d[1] - d[cur] + 1;
        ans[cc] = min(ans[cc], minw);//记录该层次的最小颜色，注意这里不能直接用=，而不用‘min’，因为一个层次到高一层次的点不是一次性更新完的，需要多次出队
    }
}

int main()
{
    while(cin >> n >> m)
    {
        for(int i = 0; i <= n; i++)
        {
            g[i].clear();
            w[i].clear();
        }
        int uu, vv, ww;
        for(int i = 0; i < m; i++)
        {
            cin >> uu >> vv >> ww;
            g[uu].push_back(vv);
            g[vv].push_back(uu);
            w[uu].push_back(ww);
            w[vv].push_back(ww);
        }
        bfs();
        bfs2();
        for(int i = 1; i < d[1]; i++)//注意输出格式，否则WA
        {
            if(i == 1)
                printf("%d", ans[i]);
            else
                printf(" %d", ans[i]);
        }
        printf("\n");
    }
    return 0;
}

方法二：一次BFS，不断回溯

思路：
从终点开始进行bfs,从一个点A到另外一点B这样进行更新，如果在更新过程中，发现某一点B已经被更新过，那么再检查它的深度，如果dep[B] = dep[A] + 1，说明B其实是属于A下一层次的点，而非在A前面的节点，那么B节点储存的信息更优还是从A到B这样的走法更优，就需要进行比较，再更新。那么我们就从B点开始回溯，假设B原来的前节点是C，那么是CB边的颜色小一些，还是AB边的颜色小一些，我们就进行比较，谁小就把谁的信息存储在B点处，如果他们俩一样，就再往前找，找A的前节点E，C的前节点D，比较EA和DC谁的颜色小，一直这样进行。那么推导到起点时，每一个节点里面都存储的最优情况的前节点，那么直接从起点开始回溯输出即可。
【双向bfs（一次可也）】【非简单图的最短路】UVa1599 Ideal Path 【紫书6-20经典例题】【无向图求字典序最小的最短路】

用邻接表保存边和颜色时，每一个点后对应的边的标号，和每一点可以延伸出的颜色的标号是一一对应的，因为每一次往g[v] 中加边的同时，也向w[v]中加入了颜色。

AC代码：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f

using namespace std;

const int maxn = 1000005;
vector<int> g[maxn], w[maxn];
int n, m, vis[maxn], d[maxn];
pair<int, int> pre[maxn];

void bfs()
{
    memset(pre, 0, sizeof(pre));
    memset(vis, 0, sizeof(vis));
    memset(d, 0, sizeof(d));
    queue<int> q;
    q.push(n);
    vis[n] = 1;
    d[n] = 1;
    pre[n] = make_pair(-1, -1);//用pair来存取某一点的前节点的标号，以及这条边在前节点里的位置
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        int len = g[cur].size();
        for(int i = 0; i < len; i++)
        {
            int t = g[cur][i];
            if(vis[t])
            {
                if(d[t] == d[cur] + 1)
                {
                    pair<int, int> x = pre[t], y = make_pair(cur, i);
                    //回溯找到颜色不同的边，注意！=-1，因为如果有两条最短的颜色全部一样，那么这里会回溯到终点，如果不停止，就会出现越界RE
                    while(x != y && x.first != -1 && y.first != -1 && w[x.first][x.second] == w[y.first][y.second])
                    {
                        x = pre[x.first];
                        y = pre[y.first];
                    }
                    if(x.first != -1 && y.first != -1 && w[x.first][x.second] > w[y.first][y.second])
                        pre[t] = make_pair(cur, i);
                }
            }
            else
            {
                vis[t] = 1;
                pre[t] = make_pair(cur, i);
                d[t] = d[cur] + 1;
                q.push(t);
            }
        }
    }
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    while(cin >> n >> m)
    {
        for(int i = 1; i <= n; i++)
        {
            g[i].clear();
            w[i].clear();
        }
        int uu, vv, ww;
        for(int i = 0; i < m; i++)
        {
            cin >> uu >> vv >> ww;
            g[uu].push_back(vv);
            g[vv].push_back(uu);
            w[uu].push_back(ww);
            w[vv].push_back(ww);
        }
        bfs();
        printf("%d\n", d[1] - 1);
        int j;
        pair<int, int> i;
        for(i = pre[1], j = 0; i.first != -1; i = pre[i.first], j++)
        {
            if(j)
                printf(" ");
            printf("%d", w[i.first][i.second]);
        }
        printf("\n");
    }
    return 0;
}