#2322477

Solution for 0596: Taxis by olphe

Source Code Status Test Cases
    Policy: public     Reviewed: 10    
05.62 sec    4084 KB    74 lines     1508 bytes    2017-05-17 18:56
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

int N, K;
list<int>edge[5000];
list<int>can;
queue<int>box;
priority_queue<long long int, vector<long long int>, greater<long long int>>Q;

int main() {
	ios::sync_with_stdio(false);
	cin >> N >> K;
	vector<int>cost(N);
	vector<int>far(N);
	vector<int>dis(N, INT_MAX);
	dis[0] = 0;
	for (int i = 0; i < N; i++)cin >> cost[i] >> far[i];
	for (int i = 0; i < K; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
	vector<int>move(N, INT_MAX);
	Q.push(0);
	while (!Q.empty()) {
		int current = Q.top() % MOD;
		int dist = Q.top() / MOD;
		box.push(current);
		for (int i = 0; i < N; i++)move[i] = INT_MAX;
		move[current] = 0;
		while (!box.empty()) {
			for (auto j : edge[box.front()]) {
				if (move[j] > move[box.front()] + 1) {
					move[j] = move[box.front()] + 1;
					box.push(j);
				}
			}
			box.pop();
		}
		for (int j = 0; j < N; j++) {
			if (move[j] && move[j] <= far[current])can.push_back(j);
		}
		for (auto i : can) {
			if (dis[i] > dist + cost[current]) {
				dis[i] = dist + cost[current];
				Q.push(dis[i] * MOD + i);
			}
		}
		can.clear();
		Q.pop();
	}
	cout << dis[N - 1] << endl;
	return 0;
}

Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 5/5 C++14 CPU: 05.62 sec Memory: 4084 KB Length: 1508 B 2017-05-17 18:56 2017-05-17 18:56
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 00.00 sec 3184 KB
Case #2: : Accepted 00.00 sec 3228 KB
Case #3: : Accepted 00.02 sec 3228 KB
Case #4: : Accepted 00.73 sec 3620 KB
Case #5: : Accepted 05.62 sec 4084 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags