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

[Poma][a]

В честь чего?
auto подставит нечто ввиде
for (set<int>::const_iterator p = myset.begin(); p != myset.end(); ++p) cout << t;

А ++p имеет сложность O(log2(n))

У нас set - дерево, отсортированное по некому критерию. Поэтому, чтобы перейти от некого элемента дерева к следующему, мы должны будет сделать порядка O(log(2)N) операций

[rrrFer]

А ++p имеет сложность O(log2(n))

откуда инфа? XDD

[Poma][a]

откуда инфа? XDD

Из здравого смысла..
Множества обычно реализуются на красно-черных деревьях. А в деревьях переход к след. элементу занимает O(log2(n)) (прув найти не смог)

[Somebody]

Так тут же вроде сортировка ре

[Somebody]

Тут же сортировка рейсов по времени отправления + один проход по ним, разве нет?

[Poma][a]

Тут же сортировка рейсов по времени отправления

Хорошо.. Отсортировали..

один проход по ним

А что делает один проход?
Есть 3 деревни
Едем из 1 в 3
Автобусы
1 0 2 5
1 1 2 3
2 3 3 5
1 1 1 10

Сортируем..
1 0 2 5
1 1 2 3
1 1 1 10
2 3 3 5

Что дальше?

[Somebody]

Мин. времена по деревням: 0, ∞, ∞
1 0 2 5
Мин. времена по деревням: 0, 5, ∞
1 1 2 3
Мин. времена по деревням: 0, 3, ∞
1 1 1 10
Мин. времена по деревням: 0, 3, ∞
2 3 3 5
Мин. времена по деревням: 0, 3, 5
Если время отправления текущего рейса не меньше минимального времени для деревни отправлдения рейса, то новое минимальное время для деревни прибытия рейса - минимум из старого времени для деревни прибытия и времени прибытия текущего рейса.

[Somebody]

Мин. времена по деревням: 0, ∞, ∞
1 0 2 5
Мин. времена по деревням: 0, 5, ∞
1 1 2 3
Мин. времена по деревням: 0, 3, ∞
1 1 1 10
Мин. времена по деревням: 0, 3, ∞
2 3 3 5
Мин. времена по деревням: 0, 3, 5
Если время отправления текущего рейса не меньше минимального времени для деревни отправления рейса, то новое минимальное время для деревни прибытия рейса - минимум из старого времени для деревни прибытия и времени прибытия текущего рейса.

[Poma][a]

Вот написал bfs..
WA 2

#include <iostream>
#include <vector>
#include <list>
#include <queue>

#define INF 10000000

using namespace std;
struct line
{
    int send_time, to, arr_time;
};

struct vill
{
    int index, time;
};

int main()
{
    int n, from, to, m;
    cin >> n >> from >> to >> m;
    vector<list<line> > bus(n+1);
    for (int i = 0; i < m; i++)
    {
        line t; int fr;
        cin >> fr >> t.send_time >> t.to >> t.arr_time;
        bus[fr].push_back(t);
    }

    vector<int> p(n+1, INF);
    vill t;
    t.index = from; t.time = 0;
    queue<vill> q;
    q.push(t);

    while (!q.empty())
    {
        vill t = q.front(); q.pop();
        for (list<line>::iterator b = bus[t.index].begin(); b != bus[t.index].end(); ++b)
        {
            if (b->send_time < t.time) continue;

			if (p[b->to] > b->arr_time+b->send_time-t.time)
            {
				p[b->to] = b->arr_time+b->send_time-t.time;
				vill temp;
                temp.index = b->to; temp.time = b->arr_time;
				q.push(temp);
            }
        }
    }

    if (p[to] != INF) cout << p[to]; 
    else cout << -1;
    return 0;
}

[Poma][a]

#include <iostream>
#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()
{
    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;
}

Теперь на 4-ом тесте