UVA 1599 Ideal Path（双向bfs+字典序+非简单图的最短路+队列判重）

https://vjudge.net/problem/UVA-1599

给一个n个点m条边(2<=n<=100000,1<=m<=200000)的无向图，每条边上都涂有一种颜色。求从结点1到结点n的一条路径，使得经过的边数尽量少，在此前提下，经过边的颜色序列的字典序最小。一对结点可能有多条边，一条边可能连接相同的结点（自环）。输入保证结点1可以到达结点n。颜色是1~10^9的整数。

分析：

从题目中我们可以看出，题目中的无向图是可以出现自环和重边的，自环我们可以在输入的时候检查并排除，但是重边我们需要保留，并从中选择颜色最小的边。
题目的数据量很大，不可能采用邻接矩阵存储图，因此应采用邻接表，且邻接表便于进行bfs
路径的颜色不代表路径的权重，本题中路径是无权的

思路：

从终点开始倒着bfs一次，得到每个点到终点的距离，然后从起点开始，按照每次距离减1的方法寻找接下来的点的编号。按照颜色最小的走，如果有多个颜色最小，则都拉入队列中，将最小的颜色记录在res数组中。

其中，index=d[0]-d[u]就得到了当前u节点对应的距离，也就是步骤数。

细节：

已经进入队列的节点不能重复入队，否则复杂度太高，会tle（重复入队的复杂度至少是O(n^2),在n=100000的情况下直接tle）
第一次bfs和第二次bfs的终止时机不同，第一次找到起点就终止，第二次则是从队列中取出节点时才能终止，为的是遍历完所有导向终点且路径长度一致的边，只有这样才能结果正确
d数组记录每个节点到终点n的距离，不能用0进行初始化，而终点处的初始化必须是0

d数组不能不初始化，否则对于多输入题目，前面的输入可能影响后面的输出

  1 #include <iostream>

  2 #include <algorithm>

  3 #include <string>

  4 #include <sstream>

  5 #include <set>

  6 #include <vector>

  7 #include <stack>

  8 #include <map>

  9 #include <queue>

 10 #include <deque>

 11 #include <cstdlib>

 12 #include <cstdio>

 13 #include <cstring>

 14 #include <cmath>

 15 #include <ctime>

 16 #include <functional>

 17 using namespace std;

 18

 19 #define maxn 100000

 20 #define inf 0x7fffffff

 21

 22 typedef struct ver

 23 {

 24     int num, color; //边的另一端的结点编号 和 颜色

 25     ver(int n, int c) : num(n), color(c) {}

 26 } Ver;

 27

 28 int n, m, a, b, c;

 29 int d[maxn], res[maxn];        //d记录每个点到终点的最短距离 res记录最短路的颜色

 30 bool vis[maxn], inqueue[maxn]; //vis每个结点是否被访问过 inqueue标记结点是否加入了队列，防止重复加入

 31 vector<Ver> edge[maxn];        //邻接表记录图

 32

 33 void bfs(int start, int end)

 34 {

 35     memset(inqueue, 0, n);

 36     memset(vis, 0, n);

 37     int u, v, c;

 38     queue<int> q;

 39     q.push(start);

 40     if (start == 0) //用于正向BFS

 41     {

 42         memset(res, 0, sizeof(int) * n);

 43         while (!q.empty())

 44         {

 45             u = q.front();

 46             q.pop();

 47             vis[u] = 1;

 48             if (u == n - 1)

 49                 return;

 50             int minc = inf, len = edge[u].size();

 51             for (int i = 0; i < len; i++)

 52                 if (!vis[v = edge[u][i].num] && d[u] - 1 == d[v])

 53                     minc = min(edge[u][i].color, minc); //获取所有路径中最小的颜色

 54             for (int i = 0; i < len; i++)

 55                 if (!vis[v = edge[u][i].num] && d[u] - 1 == d[v] && edge[u][i].color == minc && !inqueue[v])

 56                     q.push(v), inqueue[v] = 1; //若有多组颜色相同且未入队，则将其入队

 57             int index = d[0] - d[u];           //获得当前步数对应的下标

 58             if (res[index] == 0)

 59                 res[index] = minc;

 60             else

 61                 res[index] = min(res[index], minc); //获取最小颜色

 62         }

 63     }

 64     else

 65         while (!q.empty()) //用于反向DFS 构建层次图，找最短路

 66         {

 67             u = q.front();

 68             q.pop();

 69             vis[u] = 1;

 70             for (int i = 0, len = edge[u].size(); i < len; i++)

 71                 if (!vis[v = edge[u][i].num] && !inqueue[v])

 72                 {

 73                     d[v] = d[u] + 1; //一定是头一次入队，这通过inqueue保证

 74                     if (v == 0)

 75                         return;     //找到起点退出

 76                     q.push(v);      //如果不是起点，就把这个点入队

 77                     inqueue[v] = 1; //入队标记

 78                 }

 79         }

 80 }

 81

 82 int main()

 83 {

 84     while (scanf("%d%d", &n, &m) == 2)

 85     {

 86         for (int i = 0; i < n; i++)

 87             edge[i].clear();

 88         memset(d, -1, sizeof(int) * n);

 89         d[n - 1] = 0; //初始化的细节

 90         while (m--)

 91         {

 92             scanf("%d%d%d", &a, &b, &c);

 93             if (a != b) //排除自环

 94             {

 95                 edge[a - 1].push_back(ver(b - 1, c));

 96                 edge[b - 1].push_back(ver(a - 1, c));

 97             }

 98         }

 99         bfs(n - 1, 0); //先反向BFS

100         bfs(0, n - 1); //再正向BFS

101         printf("%d\n%d", d[0], res[0]);

102         for (int i = 1; i < d[0]; i++)

103             printf(" %d", res[i]);

104         printf("\n");

105     }

106     return 0;

107 }

巴特西

UVA 1599 Ideal Path（双向bfs+字典序+非简单图的最短路+队列判重）

最新文章

热门文章