george.cpp

Bài toán

Trên một đơn đồ thị, đường đi hai chiều, có một số cạnh bị cấm trong một đoạn thời gian. Hỏi mất tối thiểu bao nhiêu thời gian để đi từ S đến T.

Độ phức tạp

O((m+n) logn)

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <queue>

#include <algorithm>

using namespace std;

typedef pair<int, int> ii;

#define X first

#define Y second

bool minimize(int &a, int b){ if (a>b) a=b; else return false; return true; }

int n, m;

vector<int> a[12309];

int d[12309];

int c[2309][2309];

ii blocked[2309][2309];

int blocked_node[12309];

int n_blocked;

int extra(int u, int v, int du){

    if (blocked[u][v]==ii()) return 0;

    if (du<=blocked[u][v].X) return 0;

    if (du>=blocked[u][v].Y) return 0;

    return blocked[u][v].Y-du;

}

void dijkstra(int start, int target, int start_time){

    priority_queue<ii> qu;

    int i, u, v, du;

    for (i=1; i<=n; i++) d[i]=0x33334444;

    d[start]=start_time;

    qu.push(ii(-start_time, start));

    while (qu.size()){

        u=qu.top().second; du=-qu.top().first; qu.pop();

        if (du!=d[u]) continue;

        //printf("d[%d] = %d\n", u, d[u]);

        for (i=0; v=a[u][i]; i++)

        if (minimize(d[v], d[u]+c[u][v]+extra(u,v,d[u])))

        qu.push(ii(-d[v], v));

    }

}

main(){

    int start, target, start_time, i, p, q, w;

    scanf("%d%d", &n, &m);

    scanf("%d%d%d%d", &start, &target, &start_time, &n_blocked);

    for (i=1; i<=n_blocked; i++) scanf("%d", &blocked_node[i]);

    for (i=1; i<=m; i++){

        scanf("%d%d%d", &p, &q, &w);

        a[p].push_back(q);

        a[q].push_back(p);

        c[p][q]=c[q][p]=w;

    }

    int just=0;

    for (i=1; i<=n; i++) a[i].push_back(0);

    for (i=2; i<=n_blocked; i++){

        blocked[blocked_node[i-1]][blocked_node[i]]

        = blocked[blocked_node[i]][blocked_node[i-1]]

        = ii(just-1, just+c[blocked_node[i-1]][blocked_node[i]]);

        just += c[blocked_node[i-1]][blocked_node[i]];

    }

    dijkstra(start, target, start_time);

    printf("%d\n", d[target]-start_time);

}

Nhận xét