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