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;
}