寻找道路 noip2014D2T2

2019-11-06 07:26:04

字体：大中小

来源：转载

供稿：网友

题目描述

在有向图G 中，每条边的长度均为1 ，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：

1．路径上的所有点的出边所指向的点都直接或间接与终点连通。 2．在满足条件1 的情况下使路径最短。

注意：图G 中可能存在重边和自环，题目保证终点没有出边。

请你输出符合条件的路径的长度

Solution

感觉前几年的noip都好水=_=; 题目要求的合法点我们反向bfs就可以得到了，然后新的图做一次spfa(其实边权恒为1的话bfs也行) 水题1A

Code

#include <stdio.h>#include <string.h>#include <vector>#include <queue>#define rep(i, st, ed) for (int i = st; i <= ed; i += 1)#define erg(i, now) for (int i = ls[now]; i; i = e[i].next)#define fill(x, t) memset(x, t, sizeof(x))#define pb push_back#define N 100001#define E N * 4 + 1struct edge{int x, y, w, next;}e[E];int inQueue[N], PRt[N], dis[N], vis[N], ls[N];inline int read(){ int x = 0, v = 1; char ch = getchar(); while (ch < '0' || ch > '9'){ if (ch == '-'){ v = -1; } ch = getchar(); } while (ch <= '9' && ch >= '0'){ x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); } return x * v;}using std:: queue;inline void bfs(int st){ queue<int> que; que.push(st); fill(vis, 0); vis[st] = 1; while (!que.empty()){ int now = que.front(); que.pop(); erg(i, now){ if (!vis[e[i].y]){ vis[e[i].y] = 1; que.push(e[i].y); } } }}inline int spfa(int st, int ed){ queue<int> que; que.push(st); fill(dis, 63); dis[st] = 0; fill(inQueue, 0); inQueue[st] = 1; while (!que.empty()){ int now = que.front(); que.pop(); erg(i, now){ if (dis[now] + e[i].w < dis[e[i].y]){ dis[e[i].y] = dis[now] + e[i].w; if (!inQueue[e[i].y]){ inQueue[e[i].y] = 1; que.push(e[i].y); } } } inQueue[now] = 0; } int ret = dis[ed]; if (dis[ed] == dis[0]){ ret = -1; } return ret;}inline void addEdge(int &cnt, int x, int y, int w){ cnt += 1; e[cnt] = (edge){x, y, w, ls[x]}; ls[x] = cnt;}using std:: vector;int main(void){ int n = read(), m = read(); vector<int> x, y; rep(i, 1, m){ x.pb(read()); y.pb(read()); } int st = read(), ed = read(); int edgeCnt = 0; fill(ls, 0); rep(i, 0, x.size() - 1){ addEdge(edgeCnt, y[i], x[i], 1); } bfs(ed); edgeCnt = 0; fill(ls, 0); rep(i, 0, x.size() - 1){ addEdge(edgeCnt, x[i], y[i], 1); } rep(now, 1, n){ bool flag = true; erg(i, now){ if (!vis[e[i].y]){ flag = false; break; } } if (flag){ prt[now] = 1; } } edgeCnt = 0; fill(ls, 0); rep(i, 0, x.size() - 1){ if (prt[x[i]] && prt[y[i]]){ addEdge(edgeCnt, x[i], y[i], 1); } } int ans = spfa(st, ed); printf("%d/n", ans); return 0;}

上一篇：常用快捷键、用户管理和文件权限——linux笔记（2）

下一篇：1002 Max Sum

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注