Розвернути граф#10048

Розвернути граф (Розбір)

Побудуємо $0 - 1$ 0 - 1 граф, присвоївши наявним ребрам вагу $0$ , а їхнім зворотним ребрам — вагу $1$ . Потім запустимо пошук в ширину. Довжина найкоротшого шляху з вершини $1$ у вершину $n$ буде дорівнювати мінімальній кількості ребер, які потрібно обернути.

Приклад

Граф, наведений у прикладі, виглядає наступним чином:

Реалізація алгоритму

Оголосимо константу нескінченність.

#define INF 0x3F3F3F3F

Оголосимо масив найкоротших відстаней $d i s t$ та список суміжності графа $g$ . Для кожного ребра разом із суміжною вершиною зберігаємо вагу ребра ( $0$ або $1$ ).

vector\<int\> dist;
vector\<vector\<pair\<int, int\> \> \> g;

Функція bfs реалізує пошук в ширину з вершини $s t a r t$ .

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 (auto edge : g[v])
    {
      int to = edge.first;
      int w = edge.second;
      if (dist[to] \> dist[v] + w)
      {
        dist[to] = dist[v] + w;

C++

Залежно від ваги ребра $w$ додаємо вершину $t o$ в кінець або в початок черги.

        if (w == 1)
          q.push_back(to);
        else
          q.push_front(to);
      }
    }
  }
}

C++

Основна частина програми. Читаємо вхідні дані.

scanf("%d %d", &n, &m);
g.resize(n + 1);
for (i = 0; i \< m; i++)
{
  scanf("%d %d", &a, &b);

Орієнтованому ребру $a \to b$ a → b присвоюємо вагу $0$ , зворотному ребру присвоюємо вагу $1$ .

  g[a].push_back({ b, 0 });
  g[b].push_back({ a, 1 });
}

Запускаємо пошук в ширину з вершини $1$ .

bfs(1);

Виводимо відповідь — найкоротшу відстань до вершини $n$ .

if (dist[n] == INF)
  printf("-1\n");
else
  printf("%d\n", dist[n]);