Sometimes mysteries happen. Chef found a directed
graph with
n vertices and m edges in
his kitchen!
The evening was boring and chef has nothing else to
do, so to entertain himself, Chef thought about a question "What is the
minimum number of edges he needs to reverse in order to have at least one path
from vertex
1 to vertex n, where the vertices are numbered from 1 to n.
Input. The first line contains two space separated
integers n and m (1 ≤ n,
m ≤ 105), denoting the number of vertices and the
number of edges in the graph respectively. The i-th line of the next m lines contains two space separated integers xi and yi, (1 ≤ xi, yi ≤ n), denoting that the i-th edge connects vertices from xi to yi.
Output. In a single line, print the minimum number of
edges we need to revert. If there
is no way of having at least one path from 1 to n, print -1.
|
Sample input |
Sample output |
|
7
7 1
2 3
2 3
4 7
4 6
2 5
6 7
5 |
2 |
графы – 0 – 1 поиск в ширину
Задан
ориентированный невзвешенный граф из n вершин. Найдите наименьшее количество ребер, которое
следует развернуть так, чтобы существовал путь из 1 в n.
Пусть
(a, b) – ребро графа,
положим его вес равным 0. Для каждого такого
ребра (a, b) добавим в граф
ребро (b, a)
весом 1. Ищем кратчайший путь из 1 в n поиском в
ширину на 0-1 графе.
Реализация алгоритма
#include <cstdio>
#include <deque>
#include <vector>
#define INF 0x3F3F3F3F
using namespace std;
int tests, i, n, m, a, b, s, d;
vector<int> dist;
vector<vector<pair<int, int> > > g;
void bfs(int start)
{
dist =
vector<int>(n + 1, INF);
dist[start] =
0;
deque<int> q;
q.push_back(start);
while (!q.empty())
{
int v = q.front(); q.pop_front();
for (int i = 0; i <
g[v].size(); i++)
{
int to = g[v][i].first;
int w = g[v][i].second;
if (dist[to] > dist[v] + w)
{
dist[to] =
dist[v] + w;
if (w == 1)
q.push_back(to);
else
q.push_front(to);
}
}
}
}
int main(void)
{
scanf("%d %d", &n, &m);
g.resize(n +
1);
for (i = 0; i < m; i++)
{
scanf("%d %d", &a, &b);
g[a].push_back(make_pair(b, 0));
g[b].push_back(make_pair(a, 1));
}
bfs(1);
if (dist[n] == INF)
printf("-1\n");
else
printf("%d\n", dist[n]);
return 0;
}