QBROBOT - VOI07 Robot cứu hỏa
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<algorithm>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define fi first
#define se second
#define N 500
#define INF 1000000000
#define TR(v, it) for(typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)
int gas[N], c[N][N], n, m;
vvii g;
vvi t;
void enter() {
scanf("%d",&n);
for(int i = 0; i < n; ++i) scanf("%d", gas+i);
scanf("%d",&m); g.resize(n);
for(int i = 0; i < m; ++i) {
int u, v, l, t; scanf("%d%d%d%d", &u, &v, &l, &t);
--u; --v; c[u][v] = c[v][u] = t;
g[u].push_back(ii(v, l));
g[v].push_back(ii(u, l));
}
}
void dijkstra() {
t.resize(n); vi d = vi(n, INF); d[0] = 0;
priority_queue<ii, vii, greater<ii> > qu; qu.push(ii(0, 0));
while(!qu.empty()) {
int du = qu.top().fi, u = qu.top().se; qu.pop();
if(du > d[u]) continue;
TR(g[u], it) {
int v = it->fi, l = it->se;
if(du + l < d[v]) {
t[v] = vi(1, u);
qu.push(ii(d[v] = du + l, v));
} else if(du + l == d[v]) t[v].push_back(u);
}
}
}
bool bfs(int w) {
queue<ii> qu; qu.push(ii(n-1, w));
while(!qu.empty()) {
int u = qu.front().fi, e = qu.front().se; qu.pop();
if(u == 0) return 1;
TR(t[u], it) {
int v = *it;
if(c[u][v] <= e) qu.push(ii(v, gas[v] ? w : e - c[u][v]));
}
}
return 0;
}
void calcW() {
int lo = 0, hi = INF;
while(lo < hi) {
int mid = (lo+hi)/2;
if(bfs(mid)) hi = mid; else lo = mid + 1;
}
printf("%d\n", lo);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
enter();
dijkstra();
calcW();
return 0;
}