| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 258101 |
2020-08-05T11:07:19 Z |
Nightlight |
Cities (BOI16_cities) |
C++14 |
|
1195 ms |
61208 KB |
#include <bits/stdc++.h>
#define pii pair<long long, int>
using namespace std;
int N, K, M;
int id[10];
vector<pii> adj[100005];
long long dist[7][100005];
long long dist2[7][7][100005];
priority_queue<pii, vector<pii>, greater<pii>> pq;
void BFS(int now) {
int st = id[now];
pq.emplace(0, st);
dist[now][st] = 0;
int u, v;
long long len, w;
while(!pq.empty()) {
u = pq.top().second;
len = pq.top().first;
pq.pop();
if(dist[now][u] < len) continue;
for(pii tmp : adj[u]) {
v = tmp.second;
w = tmp.first;
if(dist[now][v] > dist[now][u] + w) {
dist[now][v] = dist[now][u] + w;
pq.emplace(dist[now][v], v);
}
}
}
}
void BFS2(int a, int b) {
for(int i = 1; i <= N; i++) {
pq.emplace(dist2[a][b][i], i);
}
int u, v;
long long len, w;
while(!pq.empty()) {
u = pq.top().second;
len = pq.top().first;
pq.pop();
if(dist2[a][b][u] < len) continue;
for(pii tmp : adj[u]) {
v = tmp.second;
w = tmp.first;
if(dist2[a][b][v] > dist2[a][b][u] + w) {
dist2[a][b][v] = dist2[a][b][u] + w;
pq.emplace(dist2[a][b][v], v);
}
}
}
}
int main() {
memset(dist, 0x3f3f3f3f, sizeof(dist));
memset(dist2, 0x3f3f3f3f, sizeof(dist2));
ios_base::sync_with_stdio(0);
cin >> N >> K >> M;
int u, v;
long long w;
for(int i = 1; i <= K; i++) cin >> id[i];
for(int i = 1; i <= M; i++) {
cin >> u >> v >> w;
adj[u].emplace_back(w, v);
adj[v].emplace_back(w, u);
}
for(int i = 1; i <= K; i++) {
BFS(i);
for(int k = 1; k <= N; k++) {
dist2[i][i][k] = dist[i][k];
}
for(int j = 1; j < i; j++) {
for(int k = 1; k <= N; k++) {
dist2[i][j][k] = dist[i][k] + dist[j][k];
}
BFS2(i, j);
}
}
for(int i = 1; i <= K; i++) {
for(int j = i + 1; j <= K; j++) {
for(int k = 1; k <= N; k++) {
dist2[i][j][k] = dist2[j][i][k];
}
}
}
long long ans = LLONG_MAX;
if(K == 2) {
ans = dist[1][id[2]];
}else if(K == 3) {
for(int i = 1; i <= N; i++) {
ans = min(ans, dist[1][i] + dist[2][i] + dist[3][i]);
}
}else if(K == 4) {
for(int i = 1; i <= N; i++) {
ans = min(ans, dist2[1][3][i] + dist2[2][4][i]);
ans = min(ans, dist2[1][2][i] + dist2[3][4][i]);
ans = min(ans, dist2[1][4][i] + dist2[2][3][i]);
}
}else {
for(int i = 1; i <= N; i++) {
ans = min(ans, dist2[1][2][i] + dist2[3][4][i] + dist[5][i]);
ans = min(ans, dist2[1][2][i] + dist2[3][5][i] + dist[4][i]);
ans = min(ans, dist2[1][2][i] + dist2[4][3][i] + dist[5][i]);
ans = min(ans, dist2[1][2][i] + dist2[4][5][i] + dist[3][i]);
ans = min(ans, dist2[1][2][i] + dist2[5][3][i] + dist[4][i]);
ans = min(ans, dist2[1][2][i] + dist2[5][4][i] + dist[3][i]);
ans = min(ans, dist2[1][3][i] + dist2[2][4][i] + dist[5][i]);
ans = min(ans, dist2[1][3][i] + dist2[2][5][i] + dist[4][i]);
ans = min(ans, dist2[1][3][i] + dist2[4][2][i] + dist[5][i]);
ans = min(ans, dist2[1][3][i] + dist2[4][5][i] + dist[2][i]);
ans = min(ans, dist2[1][3][i] + dist2[5][2][i] + dist[4][i]);
ans = min(ans, dist2[1][3][i] + dist2[5][4][i] + dist[2][i]);
ans = min(ans, dist2[1][4][i] + dist2[2][3][i] + dist[5][i]);
ans = min(ans, dist2[1][4][i] + dist2[2][5][i] + dist[3][i]);
ans = min(ans, dist2[1][4][i] + dist2[3][2][i] + dist[5][i]);
ans = min(ans, dist2[1][4][i] + dist2[3][5][i] + dist[2][i]);
ans = min(ans, dist2[1][4][i] + dist2[5][2][i] + dist[3][i]);
ans = min(ans, dist2[1][4][i] + dist2[5][3][i] + dist[2][i]);
ans = min(ans, dist2[1][5][i] + dist2[2][3][i] + dist[4][i]);
ans = min(ans, dist2[1][5][i] + dist2[2][4][i] + dist[3][i]);
ans = min(ans, dist2[1][5][i] + dist2[3][2][i] + dist[4][i]);
ans = min(ans, dist2[1][5][i] + dist2[3][4][i] + dist[2][i]);
ans = min(ans, dist2[1][5][i] + dist2[4][2][i] + dist[3][i]);
ans = min(ans, dist2[1][5][i] + dist2[4][3][i] + dist[2][i]);
ans = min(ans, dist2[2][1][i] + dist2[3][4][i] + dist[5][i]);
ans = min(ans, dist2[2][1][i] + dist2[3][5][i] + dist[4][i]);
ans = min(ans, dist2[2][1][i] + dist2[4][3][i] + dist[5][i]);
ans = min(ans, dist2[2][1][i] + dist2[4][5][i] + dist[3][i]);
ans = min(ans, dist2[2][1][i] + dist2[5][3][i] + dist[4][i]);
ans = min(ans, dist2[2][1][i] + dist2[5][4][i] + dist[3][i]);
ans = min(ans, dist2[2][3][i] + dist2[1][4][i] + dist[5][i]);
ans = min(ans, dist2[2][3][i] + dist2[1][5][i] + dist[4][i]);
ans = min(ans, dist2[2][3][i] + dist2[4][1][i] + dist[5][i]);
ans = min(ans, dist2[2][3][i] + dist2[4][5][i] + dist[1][i]);
ans = min(ans, dist2[2][3][i] + dist2[5][1][i] + dist[4][i]);
ans = min(ans, dist2[2][3][i] + dist2[5][4][i] + dist[1][i]);
ans = min(ans, dist2[2][4][i] + dist2[1][3][i] + dist[5][i]);
ans = min(ans, dist2[2][4][i] + dist2[1][5][i] + dist[3][i]);
ans = min(ans, dist2[2][4][i] + dist2[3][1][i] + dist[5][i]);
ans = min(ans, dist2[2][4][i] + dist2[3][5][i] + dist[1][i]);
ans = min(ans, dist2[2][4][i] + dist2[5][1][i] + dist[3][i]);
ans = min(ans, dist2[2][4][i] + dist2[5][3][i] + dist[1][i]);
ans = min(ans, dist2[2][5][i] + dist2[1][3][i] + dist[4][i]);
ans = min(ans, dist2[2][5][i] + dist2[1][4][i] + dist[3][i]);
ans = min(ans, dist2[2][5][i] + dist2[3][1][i] + dist[4][i]);
ans = min(ans, dist2[2][5][i] + dist2[3][4][i] + dist[1][i]);
ans = min(ans, dist2[2][5][i] + dist2[4][1][i] + dist[3][i]);
ans = min(ans, dist2[2][5][i] + dist2[4][3][i] + dist[1][i]);
ans = min(ans, dist2[3][1][i] + dist2[2][4][i] + dist[5][i]);
ans = min(ans, dist2[3][1][i] + dist2[2][5][i] + dist[4][i]);
ans = min(ans, dist2[3][1][i] + dist2[4][2][i] + dist[5][i]);
ans = min(ans, dist2[3][1][i] + dist2[4][5][i] + dist[2][i]);
ans = min(ans, dist2[3][1][i] + dist2[5][2][i] + dist[4][i]);
ans = min(ans, dist2[3][1][i] + dist2[5][4][i] + dist[2][i]);
ans = min(ans, dist2[3][2][i] + dist2[1][4][i] + dist[5][i]);
ans = min(ans, dist2[3][2][i] + dist2[1][5][i] + dist[4][i]);
ans = min(ans, dist2[3][2][i] + dist2[4][1][i] + dist[5][i]);
ans = min(ans, dist2[3][2][i] + dist2[4][5][i] + dist[1][i]);
ans = min(ans, dist2[3][2][i] + dist2[5][1][i] + dist[4][i]);
ans = min(ans, dist2[3][2][i] + dist2[5][4][i] + dist[1][i]);
ans = min(ans, dist2[3][4][i] + dist2[1][2][i] + dist[5][i]);
ans = min(ans, dist2[3][4][i] + dist2[1][5][i] + dist[2][i]);
ans = min(ans, dist2[3][4][i] + dist2[2][1][i] + dist[5][i]);
ans = min(ans, dist2[3][4][i] + dist2[2][5][i] + dist[1][i]);
ans = min(ans, dist2[3][4][i] + dist2[5][1][i] + dist[2][i]);
ans = min(ans, dist2[3][4][i] + dist2[5][2][i] + dist[1][i]);
ans = min(ans, dist2[3][5][i] + dist2[1][2][i] + dist[4][i]);
ans = min(ans, dist2[3][5][i] + dist2[1][4][i] + dist[2][i]);
ans = min(ans, dist2[3][5][i] + dist2[2][1][i] + dist[4][i]);
ans = min(ans, dist2[3][5][i] + dist2[2][4][i] + dist[1][i]);
ans = min(ans, dist2[3][5][i] + dist2[4][1][i] + dist[2][i]);
ans = min(ans, dist2[3][5][i] + dist2[4][2][i] + dist[1][i]);
ans = min(ans, dist2[4][1][i] + dist2[2][3][i] + dist[5][i]);
ans = min(ans, dist2[4][1][i] + dist2[2][5][i] + dist[3][i]);
ans = min(ans, dist2[4][1][i] + dist2[3][2][i] + dist[5][i]);
ans = min(ans, dist2[4][1][i] + dist2[3][5][i] + dist[2][i]);
ans = min(ans, dist2[4][1][i] + dist2[5][2][i] + dist[3][i]);
ans = min(ans, dist2[4][1][i] + dist2[5][3][i] + dist[2][i]);
ans = min(ans, dist2[4][2][i] + dist2[1][3][i] + dist[5][i]);
ans = min(ans, dist2[4][2][i] + dist2[1][5][i] + dist[3][i]);
ans = min(ans, dist2[4][2][i] + dist2[3][1][i] + dist[5][i]);
ans = min(ans, dist2[4][2][i] + dist2[3][5][i] + dist[1][i]);
ans = min(ans, dist2[4][2][i] + dist2[5][1][i] + dist[3][i]);
ans = min(ans, dist2[4][2][i] + dist2[5][3][i] + dist[1][i]);
ans = min(ans, dist2[4][3][i] + dist2[1][2][i] + dist[5][i]);
ans = min(ans, dist2[4][3][i] + dist2[1][5][i] + dist[2][i]);
ans = min(ans, dist2[4][3][i] + dist2[2][1][i] + dist[5][i]);
ans = min(ans, dist2[4][3][i] + dist2[2][5][i] + dist[1][i]);
ans = min(ans, dist2[4][3][i] + dist2[5][1][i] + dist[2][i]);
ans = min(ans, dist2[4][3][i] + dist2[5][2][i] + dist[1][i]);
ans = min(ans, dist2[4][5][i] + dist2[1][2][i] + dist[3][i]);
ans = min(ans, dist2[4][5][i] + dist2[1][3][i] + dist[2][i]);
ans = min(ans, dist2[4][5][i] + dist2[2][1][i] + dist[3][i]);
ans = min(ans, dist2[4][5][i] + dist2[2][3][i] + dist[1][i]);
ans = min(ans, dist2[4][5][i] + dist2[3][1][i] + dist[2][i]);
ans = min(ans, dist2[4][5][i] + dist2[3][2][i] + dist[1][i]);
ans = min(ans, dist2[5][1][i] + dist2[2][3][i] + dist[4][i]);
ans = min(ans, dist2[5][1][i] + dist2[2][4][i] + dist[3][i]);
ans = min(ans, dist2[5][1][i] + dist2[3][2][i] + dist[4][i]);
ans = min(ans, dist2[5][1][i] + dist2[3][4][i] + dist[2][i]);
ans = min(ans, dist2[5][1][i] + dist2[4][2][i] + dist[3][i]);
ans = min(ans, dist2[5][1][i] + dist2[4][3][i] + dist[2][i]);
ans = min(ans, dist2[5][2][i] + dist2[1][3][i] + dist[4][i]);
ans = min(ans, dist2[5][2][i] + dist2[1][4][i] + dist[3][i]);
ans = min(ans, dist2[5][2][i] + dist2[3][1][i] + dist[4][i]);
ans = min(ans, dist2[5][2][i] + dist2[3][4][i] + dist[1][i]);
ans = min(ans, dist2[5][2][i] + dist2[4][1][i] + dist[3][i]);
ans = min(ans, dist2[5][2][i] + dist2[4][3][i] + dist[1][i]);
ans = min(ans, dist2[5][3][i] + dist2[1][2][i] + dist[4][i]);
ans = min(ans, dist2[5][3][i] + dist2[1][4][i] + dist[2][i]);
ans = min(ans, dist2[5][3][i] + dist2[2][1][i] + dist[4][i]);
ans = min(ans, dist2[5][3][i] + dist2[2][4][i] + dist[1][i]);
ans = min(ans, dist2[5][3][i] + dist2[4][1][i] + dist[2][i]);
ans = min(ans, dist2[5][3][i] + dist2[4][2][i] + dist[1][i]);
ans = min(ans, dist2[5][4][i] + dist2[1][2][i] + dist[3][i]);
ans = min(ans, dist2[5][4][i] + dist2[1][3][i] + dist[2][i]);
ans = min(ans, dist2[5][4][i] + dist2[2][1][i] + dist[3][i]);
ans = min(ans, dist2[5][4][i] + dist2[2][3][i] + dist[1][i]);
ans = min(ans, dist2[5][4][i] + dist2[3][1][i] + dist[2][i]);
ans = min(ans, dist2[5][4][i] + dist2[3][2][i] + dist[1][i]);
}
}
cout << ans << "\n";
cin >> N;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
46464 KB |
Output is correct |
| 2 |
Correct |
23 ms |
46456 KB |
Output is correct |
| 3 |
Correct |
23 ms |
46464 KB |
Output is correct |
| 4 |
Correct |
26 ms |
46464 KB |
Output is correct |
| 5 |
Correct |
28 ms |
46456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
551 ms |
61096 KB |
Output is correct |
| 2 |
Correct |
609 ms |
60264 KB |
Output is correct |
| 3 |
Correct |
285 ms |
53996 KB |
Output is correct |
| 4 |
Correct |
96 ms |
55476 KB |
Output is correct |
| 5 |
Correct |
361 ms |
61208 KB |
Output is correct |
| 6 |
Correct |
103 ms |
55544 KB |
Output is correct |
| 7 |
Correct |
29 ms |
46712 KB |
Output is correct |
| 8 |
Correct |
27 ms |
46712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
46720 KB |
Output is correct |
| 2 |
Correct |
29 ms |
46712 KB |
Output is correct |
| 3 |
Correct |
31 ms |
46592 KB |
Output is correct |
| 4 |
Correct |
25 ms |
46720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
895 ms |
61164 KB |
Output is correct |
| 2 |
Correct |
816 ms |
60248 KB |
Output is correct |
| 3 |
Correct |
606 ms |
53996 KB |
Output is correct |
| 4 |
Correct |
485 ms |
59116 KB |
Output is correct |
| 5 |
Correct |
180 ms |
56280 KB |
Output is correct |
| 6 |
Correct |
120 ms |
57796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1195 ms |
61056 KB |
Output is correct |
| 2 |
Correct |
1157 ms |
61088 KB |
Output is correct |
| 3 |
Correct |
1090 ms |
60168 KB |
Output is correct |
| 4 |
Correct |
718 ms |
53996 KB |
Output is correct |
| 5 |
Correct |
647 ms |
59256 KB |
Output is correct |
| 6 |
Correct |
204 ms |
56144 KB |
Output is correct |
| 7 |
Correct |
113 ms |
57568 KB |
Output is correct |
