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

Download