#2325415

Solution for 0562: Shopping in JOI Kingdom by olphe

Source Code Status Test Cases
    Policy: public     Reviewed: 6    
00.05 sec    9500 KB    69 lines     1445 bytes    2017-05-19 10:22
#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, M, K;
list<int>edge[3001];
int dis[3001];
priority_queue<int, vector<int>, greater<int>>Q;
bool flag[3001];
int ans;

int main() {
	ios::sync_with_stdio(false);
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++)dis[i] = INT_MAX;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		edge[a].push_back(c * 10000 + b);
		edge[b].push_back(c * 10000 + a);
	}
	for (int i = 0; i < K; i++) {
		int a;
		cin >> a;
		dis[a] = 0;
		Q.push(a);
	}
	while (!Q.empty()) {
		int current = Q.top() % 10000;
		int far = Q.top() / 10000;
		Q.pop();
		if (flag[current])continue;
		flag[current]=true;
		for (auto i : edge[current]) {
			if (dis[i % 10000] > far + i / 10000) {
				dis[i % 10000] = far + i / 10000;
				Q.push(dis[i % 10000] * 10000 + i % 10000);
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		for (auto j : edge[i]) {
			if (abs(dis[i] - dis[j % 10000]) >= j / 10000) {
				ans = max(ans, max(dis[i], dis[i % 10000]));
			}
			else {
				ans = max(ans, max(dis[i], dis[i % 10000]) + (j / 10000 - abs(dis[i] - dis[j % 10000]) + 1) / 2);
			}
		}
	}
	cout << ans << endl;
	return 0;
}

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

Status
Judge: 25/25 C++14 CPU: 00.05 sec Memory: 9500 KB Length: 1445 B 2017-05-19 10:22 2017-05-19 10:22
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 00.00 sec 3128 KB
Case #2: : Accepted 00.00 sec 3176 KB
Case #3: : Accepted 00.00 sec 3212 KB
Case #4: : Accepted 00.00 sec 3752 KB
Case #5: : Accepted 00.00 sec 3776 KB
Case #6: : Accepted 00.03 sec 9456 KB
Case #7: : Accepted 00.03 sec 9456 KB
Case #8: : Accepted 00.03 sec 9484 KB
Case #9: : Accepted 00.03 sec 9472 KB
Case #10: : Accepted 00.03 sec 8664 KB
Case #11: : Accepted 00.03 sec 8732 KB
Case #12: : Accepted 00.03 sec 8620 KB
Case #13: : Accepted 00.02 sec 8764 KB
Case #14: : Accepted 00.02 sec 8692 KB
Case #15: : Accepted 00.04 sec 8712 KB
Case #16: : Accepted 00.05 sec 9372 KB
Case #17: : Accepted 00.05 sec 9316 KB
Case #18: : Accepted 00.04 sec 9356 KB
Case #19: : Accepted 00.04 sec 9448 KB
Case #20: : Accepted 00.03 sec 9368 KB
Case #21: : Accepted 00.04 sec 9376 KB
Case #22: : Accepted 00.05 sec 9500 KB
Case #23: : Accepted 00.05 sec 9404 KB
Case #24: : Accepted 00.04 sec 9404 KB
Case #25: : Accepted 00.05 sec 9440 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags