【UVA1599】Ideal Path理想路径--两种约束条件（!!双向bfs+非简单图的最短路+无向图邻接记录法）

题目：https://vjudge.net/problem/UVA-1599

解题思路：

---

为什么不能只用正向的bfs呢?

因为这道题是要使路径上color的字典序最小，所以最终路径上从顶点1出发的这条边的color一定是与顶点1相连的所有边color中的最小值，但是很有可能选择这条最小color边后无法到达终点，如下图：

 

双向bfs怎么用？

1.先从终点n出发，反向bfs，一旦在遍历过程中遇到起点1，则结束遍历，如下图：

入队标记数组inqueue[]   访问数组vis[]    距离(距终点长度)数组d[]

d[6]=0,其他结点都初始化为-1

以下为模拟过程：//注意是在取队首时才标记其已访问,故访问邻边(u->v)的判断条件为（!vis[v]&&!inqueue[v]）

6入队   inqueue[6]=1;

取队首6，vis[6]=1;

d[3]=d[4]=d[5]=d[6]+1=1,并将3，4，5依次入队；inqueue[3]=inqueue[4]=inqueue[5]=1;

取队首3，vis[3]=1;

d[2]=d[3]+1=2;

取队首4,vis[4]=1;

d[1]=d[4]+1=2;此时遇到起点1，结束反向bfs

故最终路径的长度为d[1]=2;

2.从起点1开始bfs，找到邻边中color最小且该条边(u->v)在1->n的路径上，即满足（d[u]-1=[v])，最小的color计为minc

如果邻边中有多条边color值=minc且这些边在1->n的路径上且另一个端点未访问未入队，则把这些边的另一个端点入队。

index=d[1]-d[u],如当u为起点1时，index=0，当u为路径上1的下一个点时，index=1，用col[index]记录最终要输出的color最小字典序，要不断更新col[index]的最小值（题目中的input正好可以体现更新col[index]的最小值）

若当前队列队首为重点，则结束正向bfs

 

为什么其他结点的d[]值都初始为-1，d[n]初始为0？

如下图：

在反向bfs时，已记录d[1]=1;

若所有的结点d[]都初始化为0时，当正向bfs时，minc=1，d[1]-1=d[2];col[0]=minc=1；且后续col[0]不会再更新

而事实上col[0]=4，这种情况就要把除终点n外的其他结点d都初始为-1

但是，d[]都初始为0在UVA上并不会WA，所以这道题实际上还是有点小bug的

 

ac代码：

---

#include <iostream>
#include <cmath>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <sstream>
#define maxn 100005
#define inf 1e+9+10
using namespace std;
typedef long long ll;
int n,m,i;
typedef struct Arc{
    int num,color;//边的另一个端点和边上的颜色值
    Arc(int n=0,int c=0):num(n),color(c){}
}arc;
vector<arc> edges[maxn];//与每个结点连接的边存入vector中
int d[maxn],col[maxn],vis[maxn],inqueue[maxn];
void bfs(int start)//u->v
{
    memset(vis,0,sizeof(vis));
    memset(inqueue,0,sizeof(inqueue));
    int v,u,len;
    queue<int> q;
    q.push(start);
    inqueue[n]=1;
    if(start==n)//反向bfs
    {
        while(!q.empty())
        {
            u=q.front();q.pop();vis[u]=1;
            len=edges[u].size();
            for(i=0;i<len;i++)
            {
                int v=edges[u][i].num;
                if(!vis[v]&&!inqueue[v])//未访问未入队
                {
                    d[v]=d[u]+1;
                    if(v==1) return ;//找到起点
                    inqueue[v]=1;
                    q.push(v);
                }

            }
        }
    }
    else//正向bfs
    {
        memset(col,0,sizeof(col));
        while(!q.empty())
        {
            u=q.front();q.pop();vis[u]=1;
            if(u==n) return ;//找到终点
            len=edges[u].size();
            int minc=inf;
            for(i=0;i<len;i++)
            {
                v=edges[u][i].num;
                if(!vis[v]&& d[u]-1==d[v])//路径中存在u->v
                    minc=min(minc,edges[u][i].color);//获取u的邻边中color的最小值
            }
            for(i=0;i<len;i++)
            {
                v=edges[u][i].num;
                if(!vis[v]&& (d[u]-1==d[v]) &&!inqueue[v] && edges[u][i].color==minc)
                {
                    inqueue[v]=1;
                    q.push(v);//多组color值相同且未入队的，要入队
                }
            }
            int index=d[1]-d[u];//求第index+1个color值
            if(col[index]==0) col[index]=minc;//未赋值
            else col[index]=min(minc,col[index]);//更新col[index]
        }
    }
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    //ios::sync_with_stdio(false);
    int a,b,c;
    while(scanf("%d %d",&n,&m)==2)
    {
        memset(d,-1,sizeof(d));
        d[n]=0;
        for(i=1;i<=n;i++)
            edges[i].clear();//不重新定义edges[]，清空即可
        while(m--)
        {
            scanf("%d %d %d",&a,&b,&c);
            if(a!=b)//排除自环
            {
                edges[a].push_back(arc(b,c));
                edges[b].push_back(arc(a,c));
            }
        }
        bfs(n);
        bfs(1);
        printf("%d\n%d",d[1],col[0]);
        for(i=1;i<d[1];i++)
            printf(" %d",col[i]);
        printf("\n");
    }
    return 0;
}