QBROBOT - VOI07 Robot cứu hỏa

Tác giả: khuc_tuan

Ngôn ngữ: C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Node {
	int v, t, c;
	Node *next;
};

int n;
int mark[505];
Node * ke[505];
int F[505], G[505];
bool inq[505];

void add( Node * & p, int v, int t, int c) {
	Node * q = new Node;
	q->v = v;
	q->t = t;
	q->c = c;
	q->next = p;
	p = q;
}

int main() {
	scanf("%d", &n);
	for(int i=1;i<=n;++i) scanf("%d", mark+i);
	mark[1] = mark[n] = 1;
	int m;
	scanf("%d", &m);
	for(int i=0;i<m;++i) {
		int u, v, t, c;
		scanf("%d%d%d%d", &u, &v, &t, &c);
		add( ke[u], v, t, c);
		add( ke[v], u, t, c);
	}
	memset( F, 0x1f, sizeof(F));
	F[1] = 0;
	queue<int> q;
	q.push(1);
	inq[1] = true;
	while(!q.empty()) {
		int u = q.front();
		inq[u] = false;
		q.pop();
		for(Node *p = ke[u]; p!=NULL; p = p->next) {
			int v = p->v;
			if(F[v]>F[u]+p->t) {
				F[v] = F[u] + p->t;
				if(!inq[v]) q.push(v), inq[v] = true;
			}	
		}	
	}
	
	int left = 0, right = 500 * 10000;
	while(left<right) {
		int mid = (left + right) / 2;
		memset( G, -1, sizeof(G));
		G[1] = mid;
		queue<int> q;
		q.push(1);
		memset( inq, false, sizeof(inq));
		inq[1] = true;
		while(!q.empty()) {
			int u = q.front();
			inq[u] = false;
			q.pop();
			for(Node *p = ke[u]; p!=NULL; p=p->next) {
				int v = p->v;
				if(F[v] == F[u] + p->t) {
					if(G[v]<G[u]-p->c) {
						G[v] = G[u] - p->c;
						if(mark[v]) G[v] = mid;
						if(!inq[v]) q.push(v), inq[v] = true;
					}
				}	
			}
		}	
		if(G[n]!=-1) right = mid;
		else left = mid + 1;
	}
	cout << left << endl;
	//system("pause");
	return 0;
}

Download