#include <bits/stdc++.h>
#define N 200050
#define int long long
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
ll inf = 200000000000000000LL, dist[N][10], dis[N], dis2[N];
ll ans = inf;
int n, m, k, C[N], id[N];
vector<pii> grafo[N];
void dijkstra(int ini)
{
int q = id[ini];
priority_queue< pii, vector< pii >, greater <pii> > pq;
for(int i = 1; i <= n; i++) dist[i][q] = inf;
dist[ini][q] = 0;
pq.push({0, ini});
while(!pq.empty())
{
int x = pq.top().s, d = pq.top().f;
//cout<<x<<" "<<q<<" "<<dist[x][q]<<"\n";
pq.pop();
if(d > dist[x][q]) continue;
for(auto v: grafo[x])
{
//cout<<"oi "<<v.f<<" "<<dist[v.f][q]<<" "<<dist[x][q] + v.s<<"\n";
if(dist[v.f][q] > dist[x][q] + v.s)
{
dist[v.f][q] = dist[x][q] + v.s;
pq.push({dist[v.f][q], v.f});
}
}
}
}
ll dijkstra2()
{
for(int i = 0; i <= n + 1; i++) dis[i] = inf;
dis[0] = 0;
priority_queue < pii, vector< pii >, greater < pii > > pq;
pq.push({0, 0});
while(!pq.empty())
{
int x = pq.top().s, d = pq.top().f;
pq.pop();
if(d > dis[x]) continue;
for(auto v: grafo[x])
{
if(dis[v.f] > dis[x] + v.s)
{
dis[v.f] = dis[x] + v.s;
pq.push({dis[v.f], v.f});
}
}
}
return dis[n + 1];
}
ll dijkstra3()
{
for(int i = 0; i <= n + 1; i++) dis2[i] = inf;
dis2[n + 1] = 0;
priority_queue < pii, vector< pii >, greater < pii > > pq;
pq.push({0, n + 1});
while(!pq.empty())
{
int x = pq.top().s, d = pq.top().f;
pq.pop();
if(d > dis2[x]) continue;
for(auto v: grafo[x])
{
if(dis2[v.f] > dis2[x] + v.s)
{
dis2[v.f] = dis2[x] + v.s;
pq.push({dis2[v.f], v.f});
}
}
}
return dis2[0];
}
void solve(int a, int b, int c, int d)
{
for(int i = 1; i <= n; i++)
{
ll A = dist[i][a] + dist[i][b], B = dist[i][c] + dist[i][d];
grafo[0].push_back({i, A});
grafo[i].push_back({0, A});
grafo[n + 1].push_back({i, B});
grafo[i].push_back({n + 1, B});
}
ans = min(ans, dijkstra2());
for(int i = 1; i <= n; i++)
{
grafo[i].pop_back();
grafo[i].pop_back();
grafo[0].pop_back();
grafo[n + 1].pop_back();
}
}
void solve2(int a, int b, int c, int d, int e)
{
for(int i = 1; i <= n; i++)
{
ll A = dist[i][a] + dist[i][b], B = dist[i][c] + dist[i][d];
grafo[0].push_back({i, A});
grafo[i].push_back({0, A});
grafo[n + 1].push_back({i, B});
grafo[i].push_back({n + 1, B});
}
dijkstra2(); dijkstra3();
for(int i = 1; i <= n; i++) ans = min(ans, dis[i] + dis2[i] + dist[i][e]);
for(int i = 1; i <= n; i++)
{
grafo[i].pop_back();
grafo[i].pop_back();
grafo[0].pop_back();
grafo[n + 1].pop_back();
}
}
int32_t main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>k>>m;
for(int i = 1; i <= k; i++) cin>>C[i], id[C[i]] = i;
for(int i = 1, a, b, c; i <= m; i++)
{
cin>>a>>b>>c;
grafo[a].push_back({b, c});
grafo[b].push_back({a, c});
}
for(int i = 1; i <= k; i++) dijkstra(C[i]);
if(k == 5)
{
for(int a = 1; a <= k; a++)
{
for(int b = a + 1; b <= k; b++)
{
for(int e = 1; e <= k; e++)
{
if(e == a or e == b) continue;
int c, d;
if(a != 1 and b != 1 and e != 1) c = 1;
if(a != 2 and b != 2 and e != 2) c = 2;
if(a != 3 and b != 3 and e != 3) c = 3;
if(a != 4 and b != 4 and e != 4) c = 4;
if(a != 5 and b != 5 and e != 5) c = 5;
if(a != 1 and b != 1 and c != 1 and e != 1) d = 1;
if(a != 2 and b != 2 and c != 2 and e != 2) d = 2;
if(a != 3 and b != 3 and c != 3 and e != 3) d = 3;
if(a != 4 and b != 4 and c != 4 and e != 4) d = 4;
if(a != 5 and b != 5 and c != 5 and e != 5) d = 5;
solve2(a, b, c, d, e);
}
}
}
}
else if(k == 4)
{
for(int a = 1; a <= k; a++)
{
for(int b = a + 1; b <= k; b++)
{
int c, d;
if(a != 1 and b != 1) c = 1;
if(a != 2 and b != 2) c = 2;
if(a != 3 and b != 3) c = 3;
if(a != 4 and b != 4) c = 4;
if(a != 1 and b != 1 and c != 1) d = 1;
if(a != 2 and b != 2 and c != 2) d = 2;
if(a != 3 and b != 3 and c != 3) d = 3;
if(a != 4 and b != 4 and c != 4) d = 4;
solve(a, b, c, d);
}
}
}
else
{
if(k == 3)
for(int i = 1; i <= n; i++) ans = min(ans, dist[i][1] + dist[i][2] + dist[i][3]);
else if(k == 2) ans = dist[C[1]][2];
}
cout<<ans<<"\n";
}
Compilation message
cities.cpp: In function 'int32_t main()':
cities.cpp:244:10: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
solve(a, b, c, d);
~~~~~^~~~~~~~~~~~
cities.cpp:244:10: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
cities.cpp:220:12: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
solve2(a, b, c, d, e);
~~~~~~^~~~~~~~~~~~~~~
cities.cpp:215:33: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(a != 2 and b != 2 and c != 2 and e != 2) d = 2;
~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
4984 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5220 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5220 KB |
Output is correct |
| 4 |
Correct |
7 ms |
5220 KB |
Output is correct |
| 5 |
Correct |
10 ms |
5292 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
394 ms |
25404 KB |
Output is correct |
| 2 |
Correct |
389 ms |
30136 KB |
Output is correct |
| 3 |
Correct |
283 ms |
30136 KB |
Output is correct |
| 4 |
Correct |
150 ms |
30136 KB |
Output is correct |
| 5 |
Correct |
332 ms |
39476 KB |
Output is correct |
| 6 |
Correct |
102 ms |
39476 KB |
Output is correct |
| 7 |
Correct |
9 ms |
39476 KB |
Output is correct |
| 8 |
Correct |
8 ms |
39476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
39476 KB |
Output is correct |
| 2 |
Correct |
13 ms |
39476 KB |
Output is correct |
| 3 |
Correct |
13 ms |
39476 KB |
Output is correct |
| 4 |
Correct |
12 ms |
39476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1638 ms |
57332 KB |
Output is correct |
| 2 |
Correct |
1801 ms |
61012 KB |
Output is correct |
| 3 |
Correct |
1183 ms |
61012 KB |
Output is correct |
| 4 |
Correct |
1012 ms |
61012 KB |
Output is correct |
| 5 |
Correct |
365 ms |
61012 KB |
Output is correct |
| 6 |
Correct |
150 ms |
61012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6058 ms |
76312 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
