Сама задача
Вкратце, у вас есть количество пунктов, начальный пункт, конечный пункт и количество ребер считываем в этом порядке. Чтобы перейти из одного пункта в другой необходимо чтобы текущее время было меньше или равно времени пункта отправления. Поскольку у нас есть машина времени, время конечного пункта может быть меньше начального. Время есть абсолютное значение и оно не превышает по модулю 10 в степени девятой.
#include <bits/stdc++.h>
using namespace std;const int sz = 1010;
const int inf = 1e9;
#define ll long long
int main(){
int n,m,a,b;
cin>>n>>a>>b>>m;
vector < vector <long long int> > e(m, vector<long long int>(4));
vector<long long int> d(sz, inf);
for (int i = 0; i <m; ++i){
cin >> e[i][0] >> e[i][1] >>e[i][2]>>e[i][3];
}
d[a] = 0;
for (int i=0; i<n; ++i)
for (int j=0; j<m; ++j)
if (e[j][1]>=d[e[j][0]]){
d[e[j][2]] = min(d[e[j][2]],e[j][3]);
}
cout<<d[b];
return 0;
}
это сам код. В общем, решение - небольшое изменение алгоритма Форда, а именно вместо длин ребер считаем время и наименьшее время текущего пункта(пункта отправления) должно быть меньше нового времени пункта отправления
В этой задаче n раундов недостаточно для нахождения оптимального пути в общем случае. Одна из причин - возможность перемещаться назад во времени. Можно рассмотреть такой набор входных данных:
2 2 2 7
1 10 2 -100
2 -5 1 10
2 -4 2 -5
2 -3 2 -4
2 -2 2 -3
2 -1 2 -2
2 0 2 -1
Здесь мы сначала небольшими шажками идём назад в прошлое, находясь в городе 2. Затем, наконец, получаем возможность переместиться в город 1, откуда уже делаем прыжок в далёкое прошлое в город 2, который и даёт нам ответ. Соответственно, нужно учесть случаи, когда число рейсов между городами больше, чем число самих городов. Во внешнем цикле по i нужно итерироваться не до n, а до максимума из n и m.
Сборка персонального компьютера от Artline: умный выбор для современных пользователей