QBROBOT - VOI07 Robot cứu hỏa

Tác giả: ladpro98

Ngôn ngữ: C++

#include <cstring>
#include <vector>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); ++it)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 505;
const int oo = 1000000009;
using namespace std;
int d1[N], dn[N];
bool recharge[N];
int n, m, limit, len;

struct edge {
    int to, t, c;
    edge(int _v, int _t, int _c) {
        to = _v; t = _t; c = _c;
    }
};
vector<edge> a[N];

void dijkstra(int source, int d[N]) {
    priority_queue<II, vector<II>, greater<II> > Q;
    Q.push(MP(0, source));
    REP(i, 1, n) d[i] = oo;
    d[source] = 0;
    while (!Q.empty()) {
        int u = Q.top().Y, du = Q.top().X; Q.pop();
        TR(it, a[u]) {
            int v = it -> to;
            int uv = it -> t;
            if (d[v] > d[u] + uv) {
                d[v] = d[u] + uv;
                Q.push(MP(d[v], v));
            }
        }
    }
}

bool ok(int u, int d, int c) {
    if (u == n) return 1;
    if (recharge[u]) c = limit;
    TR(it, a[u]) {
        int v = it -> to;
        int tuv = it -> t;
        int cuv = it -> c;
        if (d + tuv + dn[v] == len && c >= cuv && ok(v, d + tuv, c - cuv)) return 1;
    }
    return 0;
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    REP(i, 1, n) cin >> recharge[i];
    cin >> m;
    int u, v, t, c;
    FOR(i, 0, m) {
        cin >> u >> v >> t >> c;
        a[u].PB(edge(v, t, c));
        a[v].PB(edge(u, t, c));
    }
    dijkstra(1, d1); dijkstra(n, dn);
    //REP(i, 1, n) cout << d1[i] << ' '; cout << endl;
    //REP(i, 1, n) cout << dn[i] << ' '; cout << endl;
    len = d1[n];
    int l = 0, r = 1e9, ans;
    while (l <= r) {
        int mid = l + r >> 1;
        limit = mid;
        if (ok(1, 0, mid)) {
            ans = mid; r = mid - 1;
        }
        else
            l = mid + 1;
    }
    cout << ans;
    return 0;
}

Download