В Летней Компьютерной Школе (ЛКШ) построили аттракцион «Лабиринт знаний». Лабиринт представляет собой n комнат, занумерованных от 1 до n, между некоторыми из которых есть двери. Когда человек проходит через дверь, показатель его знаний изменяется на определенную величину, фиксированную для данной двери. Вход в лабиринт находится в комнате 1, выход — в комнате n. Каждый ученик проходит лабиринт ровно один раз и попадает в ту или иную учебную группу в зависимости от количества набранных знаний (при входе в лабиринт этот показатель равен нулю). Ваша задача показать наилучший результат.
Пример
| Входные данные | Выходные данные |
| 2 2
1 2 5 1 2 -5 |
5 |
| 5 5
1 2 5 2 4 5 4 5 5 3 3 5 2 3 5 |
15 |
| 3 3
1 2 5 1 2 -5 2 2 6 |
🙁 |
| 3 3
1 2 2 2 3 3 3 1 4 |
🙂 |
Решение
|
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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include <iostream> #include <vector> #include <climits> using namespace std; struct edge { int start,finish,cost; }; int main() { int n,m; cin>>n>>m; vector<edge>e; for (int i=0;i<m;i++) { edge a; cin>>a.start>>a.finish>>a.cost; a.start--; a.finish--; e.push_back(a); } vector<int> length (n, INT_MIN); vector<int> p (n, -1); length[0] = 0; int x; for (int i=0;i<n;i++) { x = -1; for (int j=0;j<m;j++) if ((length[e[j].start]>INT_MIN)&&(length[e[j].finish]<length[e[j].start] + e[j].cost)) { length[e[j].finish]=length[e[j].start] + e[j].cost; p[e[j].finish]=e[j].start; x=1; } } vector<int> path; int k=0; for (int i=n-1;i!=-1;i=p[i]) { k++; path.push_back (i); if(k>n) break; } if(length[n-1]==INT_MIN) cout<<":("<<endl; else if((x!=-1)&&((path.back()!=0)||(path.front()!=n-1)||(k>n))) cout<<":)"<<endl; else cout<<length[n-1]<<endl; return 0; } |
Создадим вектор расстояний length на n элементов. Все элементы кроме 0-го приравниваем к минимальному числу. Нулевой элемент приравниваем к 0. Также создадим вектор p в котором будем хранить номер вершины из которой мы попали в текущую. Затем в цикле проходим по всем вершинам и в вектор length записываем расстояние за которое мы дошли в эту вершину. n-1 элемент вектора и будет ответом задачи. Затем мы восстанавливаем путь из нулевой вершины в последнюю, но будем это делать не более n раз. Затем проверяем, если в последней вершине значение не изменилось то выводим :(. Затем проверяем был ли в пути цикл, если да то выводи :), в противном случае выводим значение length[n-1].