2968. Кратчайшие пути

Задан взвешенный ориентированный граф и вершина s в нём. Для каждой вершины u выведите длину кратчайшего пути от s до u.

Вход. Первая строка содержит три целых числа n, m, s (2 ≤ n ≤ 2000, 1 ≤ m ≤ 5000) – количество вершин и рёбер в графе и номер начальной вершины соответственно.

Следующие m строк описывают рёбра графа. Каждое ребро задаётся тремя числами – начальной вершиной, конечной вершиной и весом ребра соответственно. Вес ребра – целое число, не превосходящее 10¹⁵ по абсолютной величине. В графе могут быть кратные рёбра и петли.

Выход. Выведите n строк – для каждой вершины u выведите длину кратчайшего пути из s в u. Если не существует пути между s и u, выведите "*". Если не существует кратчайшего пути между s и u, выведите "-".

Пример входа	Пример выхода
6 7 1 1 2 10 2 3 5 1 3 100 3 5 7 5 4 10 4 3 -18 6 1 -1	0 10 - - - *

РЕШЕНИЕ

графы – алгоритм Беллмана - Форда

Анализ алгоритма

Запустим алгоритм Беллмана - Форда. Если некоторая вершина u не достигнута из s, то пути между s и u не существует. Рассмотрим все ребра j → to, которые релаксируют. Это означает, что от s до to не существует кратчайшего пути. Также не существует кратчайшего пути от s до всех вершин, достижимых из to (такие вершины ищем поиском в глубину).

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

Объявим глобальные массивы. Взвешенный граф храним в списке смежности g.

#define MAX 5010

int used[MAX];

long long w, d[MAX];

long long INF = 0x3F3F3F3F3F3F3F3FLL;

struct node

{

int to;

long long dist;

node(int to, long long dist) : to(to), dist(dist) {};

};

vector<vector<node> > g;

Алгоритм Беллмана – Форда.

void Bellman_Ford(void)

{

int i, j, k;

memset(d,0x3F,sizeof(d));

Алгоритм запускаем со стартовой вершины s.

d[s] = 0;

Совершаем n итераций.

for(i = 1; i <= n; i++)

Перебираем все ребра.

for(j = 1; j <= n; j++)

for (k = 0; k < g[j].size(); k++)

{

int to = g[j][k].to;

long long dist = g[j][k].dist;

Релаксируем текущее ребро j → to.

if ((d[j] < INF) && (d[to] > d[j] + dist))

d[to] = d[j] + dist;

}

}

Поиск в глубину из вершины v. Пройденные вершины отмечаем в массиве used.

void dfs(int v)

{

used[v] = 1;

for(int i = 0; i < g[v].size(); i++)

{

int to = g[v][i].to;

if (!used[to]) dfs(to);

}

}

Основная часть программы. Читаем входной ориентированный взвешенный граф.

scanf("%d %d %d",&n,&m,&s);

g.resize(n+1);

for(i = 1; i <= m; i++)

{

scanf("%d %d %lld",&u,&v,&w);

g[u].push_back(node(v,w));

}

Запускаем алгоритм Беллмана – Форда.

Bellman_Ford();

Перебираем все ребра графа.

memset(used,0,sizeof(used));

for(i = 1; i <= n; i++)

for(j = 0; j < g[i].size(); j++)

{

int to = g[i][j].to;

long long dist = g[i][j].dist;

Если ребро j → to релаксирует, то расстояние от s до to равно минус бесконечности. Также минус бесконечности равно расстояние от s до всех вершин, достижимых из to. Все такие вершины v, достижимые из to, отметим used[v] = 1 при поиске в глубину dfs(to).

if ((d[i] < INF) && (d[to] > d[i] + dist) && !used[to])

dfs(to);

}

Выводим ответ.

for(i = 1; i <= n; i++)

{

if (d[i] == INF) printf("*\n");

else if (used[i]) printf("-\n");

else printf("%lld\n",d[i]);

}