理想路径——双向BFS

题目

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

解题思路

方法是从终点开始倒着BFS，得到每个结点 i 到终点的最短距离d[i]。然后直接从起点开始走，但是每次到达一个新结点时要保证d值恰好减少1,直到到达终点，这样得到的一定是一条最短路。

有了上述结论，可以这样解决：直接从起点开始按照上述规则走，如果有多种走法，选择颜色字典序最小的走；如果有多条边的颜色字典序都最小，则记录所有这些边的终点，走下一步时要考虑从所有这些点出发的边。这实际上是又做了一次BFS，因此时间复杂度仍为 O(m)。

代码实现

 #include<stdio.h>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 #include<queue>

 using namespace std;

 const int maxn =  + ;

 vector<int>G[maxn];

 vector<int>C[maxn];

 int n, m,vis[maxn], d[maxn], ans[maxn];        //d保存距离，ans保存最小距离

 void init()

 {

     int x, y;

     int tmp;

     memset(vis, , sizeof(vis));

     memset(d, , sizeof(d));

     memset(ans, , sizeof(ans));

     for (int i = ; i <=n; i++)  G[i].clear();

     for (int i = ; i <= n; i++)  C[i].clear();

     for (int i = ; i < m; i++)

     {

         cin >> x >> y;

         G[x].push_back(y); G[y].push_back(x);

         cin >> tmp;

         C[x].push_back(tmp); C[y].push_back(tmp);

     }

 }

 void bfs1()    //进行距离的遍历，得到d数组

 {

     memset(d, -, sizeof(d));

     queue<int>q;

     d[n] = ;

     q.push(n);

     while (!q.empty())

     {

         int u = q.front(); q.pop();

         int sz = G[u].size();

         for (int i = ; i < sz; i++)

         {

             int v = G[u][i];

             if (d[v] == -)

             {

                 d[v] = d[u] + ;

                 q.push(v);

             }

         }

     }

     return;

 }

 void bfs2()    //对颜色进行排序，并保存颜色

 {

     memset(vis, , sizeof(vis));

     queue<int>q;

     q.push();

     while (!q.empty())

     {

         int u = q.front(); q.pop();

         if (d[u] == )  return;

         int sz = G[u].size();

         int mm = -;

         for (int i = ; i < sz; i++)

         {

             int v = G[u][i];

             if (d[v] == d[u] - )

             {

                 if (mm == -)  mm = C[u][i];

                 else  mm = min(mm, C[u][i]);

             }

         }

         int t = d[] - d[u];

         if (ans[t] == )  ans[t] = mm;

         else  ans[t] = min(ans[t], mm);

         for (int i = ; i < sz; i++)   //将所有同时满足条件的节点加入队列，并同时进行bfs

         {

             int v = G[u][i];

             if (vis[v] == false && d[v] == d[u] -  && C[u][i] == mm)

             {

                 q.push(v);

                 vis[v] = true;

             }

         }

     }

     return;

 }

 int main()

 {

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

     {

         init();

         bfs1();

         bfs2();

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

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

         {

             if (i)  printf(" ");

             printf("%d", ans[i]);

         }

         printf("\n");

     }

     return ;

 }

参考链接：https://blog.csdn.net/cfarmerreally/article/details/52128440

巴特西

理想路径——双向BFS

最新文章

热门文章