Не проходит 17 тест на acmp

334
23 августа 2018, 09:40

Сама задача

Вкратце, у вас есть количество пунктов, начальный пункт, конечный пункт и количество ребер считываем в этом порядке. Чтобы перейти из одного пункта в другой необходимо чтобы текущее время было меньше или равно времени пункта отправления. Поскольку у нас есть машина времени, время конечного пункта может быть меньше начального. Время есть абсолютное значение и оно не превышает по модулю 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;
}

это сам код. В общем, решение - небольшое изменение алгоритма Форда, а именно вместо длин ребер считаем время и наименьшее время текущего пункта(пункта отправления) должно быть меньше нового времени пункта отправления

Answer 1

В этой задаче 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.

READ ALSO
ГОСТ 28147-89 (Режим простой замены). (C++) - CUDA

ГОСТ 28147-89 (Режим простой замены). (C++) - CUDA

В программе реализовывается алгоритм шифрования ГОСТ 28147-89 в режиме простой заменыИзначально хотел сделать шифрование и дешифрование на CPU и на GPU

263
Как прилинковать нестандартную версию boost через cmake (не хедеронли часть).

Как прилинковать нестандартную версию boost через cmake (не хедеронли часть).

Есть проект под arm который компилируется и собирается на х86ой машине (кросскомпиляция)Есть версия библиотеки boost собранная под arm

221
Как сделать метод универсальным?

Как сделать метод универсальным?

Пишу метод упрощающий чтение кода и никак не могу сделать его так, что бы он был универсальный

214
Не работает socket receive

Не работает socket receive

Пробую сделать бота на java для торгового терминала quikДля того чтобы передавать информацию из квика в java сделал сокет клиент на lua, вот его код:

206