#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const long long inf = 1e18;
int n, k, m, in[N];
vector <int> vec;
vector <pair <int, int> > g[N];
long long dist[5][N], dist2[5][5][N];
void dijkstra (int s, int ind) {
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > pq;
for (int i = 1; i <= n; i++) dist[ind][i] = inf;
dist[ind][s] = 0; pq.push({dist[ind][s], s});
while (!pq.empty()) {
pair <long long, int> val = pq.top(); pq.pop();
long long d = val.first;
int u = val.second;
if (d == dist[ind][u]) {
for (auto v: g[u]) {
if (dist[ind][v.second] > dist[ind][u] + v.first) {
dist[ind][v.second] = dist[ind][u] + v.first;
pq.push({dist[ind][v.second], v.second});
}
}
}
}
}
void redijkstra (int s, int t) {
priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > pq;
for (int i = 1; i <= n; i++) {
dist2[in[s]][in[t]][i] = dist[in[s]][i] + dist[in[t]][i];
pq.push({dist2[in[s]][in[t]][i], i});
}
while (!pq.empty()) {
pair <long long, int> val = pq.top(); pq.pop();
long long d = val.first;
int u = val.second;
if (d == dist2[in[s]][in[t]][u]) {
for (auto v: g[u]) {
if (dist2[in[s]][in[t]][v.second] > dist2[in[s]][in[t]][u] + v.first) {
dist2[in[s]][in[t]][v.second] = dist2[in[s]][in[t]][u] + v.first;
pq.push({dist2[in[s]][in[t]][v.second], v.second});
}
}
}
}
}
int main(){
scanf("%d %d %d", &n, &k, &m);
for (int i = 1; i <= k; i++) {
int x;
scanf("%d", &x);
vec.push_back(x);
}
sort(vec.begin(), vec.end());
vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
k = vec.size();
for (int i = 0; i < vec.size(); i++) in[vec[i]] = i;
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
g[u].push_back({w, v});
g[v].push_back({w, u});
}
for (int i = 0; i < vec.size(); i++) dijkstra(vec[i], i);
if (k == 2) printf("%lld", dist[in[vec[0]]][vec[1]]);
else if (k == 3) {
long long ans = 1e18;
for (int i = 1; i <= n; i++) ans = min(ans, dist[in[vec[0]]][i] + dist[in[vec[1]]][i] + dist[in[vec[2]]][i]);
ans = min(ans, dist[in[vec[0]]][vec[1]] + dist[in[vec[1]]][vec[2]]);
ans = min(ans, dist[in[vec[0]]][vec[1]] + dist[in[vec[0]]][vec[2]]);
ans = min(ans, dist[in[vec[0]]][vec[2]] + dist[in[vec[1]]][vec[2]]);
printf("%lld", ans);
}
else {
long long ans = 1e18;
for (int i = 0; i < vec.size(); i++) for (int j = i + 1; j < vec.size(); j++) redijkstra(vec[i], vec[j]);
if (k == 4) {
do {
long long ans = 1e18;
for (int i = 1; i <= n; i++) if (in[vec[0]] < in[vec[1]] && in[vec[2]] < in[vec[3]] && in[vec[0]] < in[vec[2]]) ans = min(ans, dist2[in[vec[0]]][in[vec[1]]][i] + dist2[in[vec[2]]][in[vec[3]]][i]);
} while (next_permutation(vec.begin(), vec.end()));
printf("%lld", ans);
}
else {
do {
long long ans = 1e18;
for (int i = 1; i <= n; i++) if (in[vec[0]] < in[vec[1]] && in[vec[2]] < in[vec[3]] && in[vec[0]] < in[vec[2]]) ans = min(ans, dist2[in[vec[0]]][in[vec[1]]][i] + dist2[in[vec[2]]][in[vec[3]]][i] + dist[in[vec[4]]][i]);
} while (next_permutation(vec.begin(), vec.end()));
printf("%lld", ans);
}
}
return 0;
}
/*
4 3 6
1 3 4
1 2 4
1 3 9
1 4 6
2 3 2
2 4 5
3 4 8
*/
Compilation message
cities.cpp: In function 'int main()':
cities.cpp:66:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vec.size(); i++) in[vec[i]] = i;
~~^~~~~~~~~~~~
cities.cpp:74:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vec.size(); i++) dijkstra(vec[i], i);
~~^~~~~~~~~~~~
cities.cpp:87:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vec.size(); i++) for (int j = i + 1; j < vec.size(); j++) redijkstra(vec[i], vec[j]);
~~^~~~~~~~~~~~
cities.cpp:87:68: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vec.size(); i++) for (int j = i + 1; j < vec.size(); j++) redijkstra(vec[i], vec[j]);
~~^~~~~~~~~~~~
cities.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &k, &m);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
cities.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &u, &v, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2752 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
2896 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
345 ms |
13336 KB |
Output is correct |
| 2 |
Correct |
366 ms |
14356 KB |
Output is correct |
| 3 |
Correct |
123 ms |
14356 KB |
Output is correct |
| 4 |
Correct |
95 ms |
14356 KB |
Output is correct |
| 5 |
Correct |
286 ms |
14356 KB |
Output is correct |
| 6 |
Correct |
101 ms |
14356 KB |
Output is correct |
| 7 |
Correct |
6 ms |
14356 KB |
Output is correct |
| 8 |
Correct |
6 ms |
14356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
948 ms |
23428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1388 ms |
27380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
