欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-12 09:50:38
...

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

解题思路:


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

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

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

 

双向bfs怎么用?

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

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

入队标记数组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?

如下图:

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

在反向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;
}