## #2325415

Solution for 0562: Shopping in JOI Kingdom by olphe

Source Code Status Test Cases
Policy: public     Reviewed: 17
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 #  ( | )