Условие
Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют. Требуется посчитать длины кратчайших путей от вершины номер [latex]1[/latex] до всех остальных вершин.
Сначала записано количество вершин графа [latex]n[/latex] ([latex]1 \leq n \leq 100[/latex]), за которым идет количество ребер [latex]m[/latex] ([latex]1 \leq m \leq 10000[/latex]) Следующие [latex]m[/latex] троек чисел описывают ребра: начало ребра, конец ребра и его вес (вес — целое число от [latex]-100[/latex] до [latex]100[/latex]).
Выведите [latex]n[/latex] чисел — расстояния от вершины номер [latex]1[/latex] до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число [latex]30000[/latex].
Тестирование
| № | Входные данные | Выходные данные |
| 1 | 4 5 1 2 10 2 3 10 1 3 100 3 1 -10 2 3 1 |
0 10 11 30000 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <vector> #include <cmath> using namespace std; struct edge { int a, b, cost; edge(int na, int nb, int nc) { int a = na; int b = nb; int cost = nc; } }; const int INF = 30000; int main() { int n, m, a, b, c; vector<edge> e; cin >> n >> m; for(int i = 0; i < m; i++) { cin >> a >> b >> c; edge newEdge(a, b, c); e.push_back(newEdge); } vector<int> d(n, INF); d[0] = 0; for(int i = 0; i < n - 1; i++) for(int j = 0; j < m; j++) if(d[e[j].a] < INF) d[e[j].b] = min(d[e[j].b], d[e[j].a] + e[j].cost); for(int i = 0; i < n - 1; i++) cout << d[i] << ' '; return 0; } |
Решение
Отметим, что сохранять значение наибольших граней в массив, как указывается в условии, необязательно, так как значение длины максимальной грани можно обновлять по ходу нахождения граней подстрок.
В основе программы лежит алгоритм, идея которого заключается не в переборе подстрок с последующим поиском граней в них (так как это было бы очень ресурсозатратно), а в переборе смещений префикса и суффикса друг относительно друга и вычислении максимальной грани, которую можно получить в каждом из таких смещений. Цикл перебора выглядит следующим образом:
- Так как по условию грань не может совпадать со строкой, перебор начнем со случая, когда первый символ суффикса находится на второй позиции в строке, а первый символ префикса — на первой позиции. В каждой следующей итерации первый символ суффикса будет смещаться на одну позицию вправо, но первый символ префикса будет неизменно оставаться на первой позиции. Цикл продолжается до тех пор, пока не дойдем до случая, когда первый символ суффикса будет последним символом строки, и пока количество символов от начала суффикса до конца строки будет больше длины максимальной найденной на данный момент грани (это условие необязательно, но оно ускоряет работу программы, отбрасывая варианты, когда получить более длинную грань уже никаким образом не получится):
1234567for(int i = 1; i < s.length() && s.length() - i > max; i++) {int j = 0;/*Перебираем различные длины префиксов (суффиксов), пока не дойдем до длины 1 и пока можем встретить грань, длиннее хранящейся.i - первый символ очередного суффиксаj - длина текущей грани и первый символ очередного префикса*/ - Начнем параллельно «двигаться» вправо по строке, проверяя на совпадение соответствующие символы префикса и суффикса и продолжая до тех пор, пока не наткнемся на различные символы или пока не дойдем до конца строки. При этом будем попутно накапливать значение длины текущей грани, пока пары символов совпадают. К примеру, если в очередной итерации первые символы префикса и суффикса — это первый и третий символы строки соответственно, то сначала проверим на совпадение символы на позициях 1 и 3, затем 2 и 4, 3 и 5 и т. д.
В виду того, что нумерация символов в строке начинается с нуля, переменная j выполняет здесь одновременно роль первого символа префикса и длины текущей грани.12while(j < s.length() - i && s.at(j) == s.at(i + j))j++; - Сравним длину текущей грани с длиной максимальной грани и, если необходимо, обновим значение максимальной.
Отметим, что значение переменной j, получаемое в каждой итерации, представляет собой максимально возможную длину грани либо исходной строки (если проверки на совпадение пар символов закончились из-за достижения конца строки), либо подстроки, получаемой путем отбрасывания правой части исходной до того символа, на котором обнаружилось несовпадение.
Ссылки
Условие задачи на E-Olymp;
Код программы на Ideone.com;
Подтверждение решения на E-Olymp.