Menu
翘楚小站
  • 主页
  • 小项目
  • 算法
  • 摄影
翘楚小站

[NOIP2014]寻找道路(road)

Posted on 2019年11月12日 by WonderBoy

传送门:洛谷P2296 | MFOJ
作者:xzqiaochu

Solution

一道没有背景的题目……

这是一道最短路的变式题,要先要排除一些非法的点。

http://static.xzzhangqiaochu.top/images/road.png

如上图所示,我们考虑建立反向边,从终点向起点跑一遍最短路算法(其实BFS就行)。
绿色叉叉的两个点无法被访问,说明这两个点无法通向终点。如果存在一个点指向他们,那么这个点是非法的。(即图中蓝色叉叉的点是非法的)

去除非法的点后,再跑一遍最短路算法就可以啦~

Code

//[NOIP2014]-Day2-B-寻找道路(road)
//http://www.mfstem.org/contest/19/problem/A
//author: xzqiaochu
//status: AC
//algorithm: 通过反向边删除非法的点 
//time: 2019/11/12
#include <cstdio>
#include <cstring> 
#include <utility>
#include <queue>
using std::priority_queue;
using std::pair;
using std::make_pair; 
const int VSZ = 1e4 + 7, MSZ = 2e5 + 7;
const int INF = 0x3f3f3f3f, EPS = 100;

int n, m, s, t;

int tot, head[VSZ];
struct Edge {
    int x, y, next;
} edge[MSZ];

int dis[VSZ];
bool vis[VSZ], not_use[VSZ];

inline void addEdge(int x, int y) {
    edge[++tot].x = x, edge[tot].y = y;
    edge[tot].next = head[x], head[x] = tot;
}

void Dijkstra(int sta, int tar) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    priority_queue< pair<int, int> > q;
    dis[sta] = 0;
    q.push(make_pair(0, sta));
    while (!q.empty()) {
        int x = q.top().second; q.pop();
        if (vis[x])
            continue;
        vis[x] = true;
        for (int i = head[x]; i; i = edge[i].next) {
            int y = edge[i].y;
            if (!not_use[y] && dis[x] + 1 < dis[y]) {
                dis[y] = dis[x] + 1;
                q.push(make_pair(-dis[y], y));
            }
        }
    }
}

int main() {
//  freopen("road.in", "r", stdin);
//  freopen("road.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        addEdge(y, x); //添加反向边
    }
    scanf("%d%d", &s, &t);

    Dijkstra(t, s);

    memset(head, 0, sizeof(head)), tot = 0; //清空链式前向星,重新建图
    for (int i = 1; i <= m; i++) {
        if (vis[edge[i].x] == false) //反向边终点未被访问 => 边i未被访问 =>
            not_use[edge[i].y] = true; //(在正向图中)边i无法通向终点 => 该边的起点是非法的 
        addEdge(edge[i].y, edge[i].x); //一个for循环就可以
    }

    Dijkstra(s, t);
    if (dis[t] > INF - EPS)
        printf("-1");
    else
        printf("%d", dis[t]);
    return 0;
}
  • NOIP
  • 信息学
  • 图论
  • 最短路
  • 发表评论 取消回复

    电子邮件地址不会被公开。 必填项已用*标注

    标签

    Arduino CSP DIY NOIP python tensorflow 一中文创 二分 人工智能 信息学 动态规划 图论 徐州一中 摄影 撷秀极客社区 数学 数论 最短路 树 模拟 洛谷 电子 短片 航拍 递归

    分类目录

    文章归档

    近期评论

    • 王清筠发表在《【徐州一中】再一次出发》
    • 王清筠发表在《测绘伏安特性曲线(I-U图像)》
    • xzqiaochu发表在《测绘伏安特性曲线(I-U图像)》
    • xzqiaochu发表在《测绘伏安特性曲线(I-U图像)》
    • 晨鹤发表在《测绘伏安特性曲线(I-U图像)》

    友情链接

    清筠小站
    晨鹤小站(。・∀・)ノ゙

    ©2021 翘楚小站 | 苏ICP备18005311号 | Powered by WordPress & Superb Themes