M_sea

洛谷1811 最短路
题目描述给定一个包含N个点,M条边的无向图,每条边的边权均为1。 再给定K个三元组(A,B,C),表示从A点走到B...
扫描右侧二维码阅读全文
09
2017/09

洛谷1811 最短路

题目描述

给定一个包含N个点,M条边的无向图,每条边的边权均为1。

再给定K个三元组(A,B,C),表示从A点走到B点后不能往C点走。注意三元组是有序的,如可以从B点走到A点再走到C。

现在你要在K个三元组的限制下,找出1号点到N号点的最短路径,并输出任意一条合法路径,会有Check检查你的输出

传送门

算法

如果不考虑三元组的限制,那么这就是一道普及难度的单源最短路问题。
但是本题有了三元组的限制,难度就升高了(但也没到省选难度)

Dijkstra的思路和广搜是类似的,所以我们考虑广搜。
从1号节点开始,对于每个状态:记录其节点编号、步数和父状态。

因为要记录父状态,所以最好手打队列。

再来考虑一下三元组和路径:
用$g[i] [j]$来表示i到j有没有路径。
用$no[i] [j]$来表示三元组(i,j,x)中的x。

这样子在Bfs时的条件就变得比较好打了。

注意到第一个状态的父状态指针为NULL,在判三元组时要注意(不然会访问非法内存)。

路径如何输出?递归即可。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
#define re register
using namespace std;
int no[3010][3010];
int g[3010][3010];
int n,m,k;
struct node //队列用
{
    int now,s;
    node *fa;
    node()
    {
        this->now=0;
        this->fa=NULL;
        this->s=0;
    }
}q[100010]; //队列
inline int read() //读入优化
{
    int X=0,w=1; char ch=0;
    while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}
void Init() //输入、建图、建三元组
{
    n=read(); m=read(); k=read();
    int u,v,t;
    for (re int i=1;i<=m;i++)
    {
        u=read(); v=read();
        g[u][v]=g[v][u]=1;
    }
    for (re int i=1;i<=k;i++)
    {
        u=read(); v=read(); t=read();
        no[u][v]=t;
    }
}
void Print(node *k) //输出路径,递归,使用了指针
{
    if (k->fa!=NULL) Print(k->fa); //有父状态就往前递归
    printf("%d ",k->now); //输出当前节点
}
void Bfs()
{
    int head=0,tail=1; //头尾指针
    node x; x.now=1; x.fa=NULL; x.s=0; q[1]=x; //初状态
    while (head<tail) //Bfs的模板
    {
        head++; x=q[head];
        for (re int i=1;i<=n;i++) //扩展节点
        {
            if (g[x.now][i]&&no[(x.fa==NULL)?0:(x.fa)->now][x.now]!=i&&i!=x.now) 
                        //首先是有路径,然后是符合三元组(特判NULL),最后这两个点不能相同
            {
                node y; y.now=i; y.s=x.s+1; y.fa=&q[head]; //记录新节点
                tail++; q[tail]=y; //入队
                if (i==n) //如果到了就输出,然后return
                {
                    printf("%d\n",q[tail].s);
                    Print(&y);
                    return;
                }
            }
        }
    }
}
int main()
{
    Init(); //初始化
    Bfs(); //广搜
    return 0;
}
最后修改:2018 年 11 月 09 日 04 : 07 PM

发表评论