Задача на графы : "Автобусы" с acmp.ru

[Poma][a]

#include <fstream>
#include <vector>
#include <algorithm>
 
#define INF 10000000
 
using namespace std;
 
struct line
{
    int from, send_time, to, arr_time;
};
 
bool cmp(const line a, const line b)
{
    return a.send_time < b.send_time;
}
 
int main()
{
    ifstream cin("input.txt");
    ofstream cout("output.txt");
 
    int n, from, to, m;
    cin >> n >> from >> to >> m;
 
    vector<line> b(m);
    vector<int> p(n+1, INF);
    p[from] = 0;
 
    for (int i = 0; i < m; i++)
        cin >> b[i].from >> b[i].send_time >> b[i].to >> b[i].arr_time;
 
    sort(b.begin(), b.end(), cmp);
 
    for (int i = 0; i < m; i++)
        if (b[i].send_time >= p[b[i].from]) p[b[i].to] = min(p[b[i].to], b[i].arr_time);
 
 
    if (p[to] != INF)
        cout << p[to];
    else cout << -1;
}

Бинго! Прошло..
Разница в одном символе.. (Надо заканчивать писать ночью)..
Спасибо!

[rrrFer]

эм, дак я чем-то помог ?

[Poma][a]

эм, дак я чем-то помог ?

Ну.. Вы предложили прекрасную идею.. А то, что она не работает, скорее всего виноват исключительно я.. Снова косякнул.. или не придумал хорошего контр. примера..

Вариант Somebody я до сих пор не понимаю.. Не понимаю почему это работает.. и работает правильно..
(Ведь если есть путь из a в b и из b в c.. маршрут начинается в момент времени T. И едет автобус из a в b за 0.. Но мы отсортировали таким макаром, что b->c стоит раньше.. и тогда т.к. в p[b] стоит INFINITY, что мы даже не будем смотреть это ребро.. Я прав?)
Получается, что если что так можно искать минимальный путь в графе?? (наверное с неким ограничением на ребра..)..

[Somebody]

Да, что-то я не подумал о таком Видимо, там тестов на это не было.
Тогда можно, например, для каждой группы рейсов с нулевым временем сначала делать топологическую сортировку.

[Somebody]

Да, что-то я не подумал о таком :( Видимо, там тестов на это не было.
Тогда можно, например, для каждой группы рейсов с нулевым временем делать поиск в глубину.

[Poma][a]

для каждой группы рейсов с нулевым временем сначала делать топологическую сортировку.

для каждой группы рейсов с нулевым временем делать поиск в глубину.

Всё же что именно?

P.S. Если вдруг, кому-то захочется поразбирать чужой корявый код, то прошу к посту 24

[Somebody]

Сообщение от 'Poma

Всё же что именно?

Поиск в глубину. Хотя топологическая сортировка тоже реализуется через поиск в глубину - просто лишняя работа потом ещё будет.