#include <bits/stdc++.h>
#define N 200050
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<int, ll> pii;
ll inf = 200000000000000000LL, dist[N][10], dis[N][6][6], dis2[N][6][6];
ll ans = inf;
int n, m, k, C[N], id[N];
vector<pii> grafo[N];
inline 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())
{
ll 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});
}
}
}
}
bool calc[6][6], calc2[6][6];
inline ll dijkstra2(int a, int b)
{
if(calc2[a][b]) return dis[n + 1][a][b];
calc2[a][b] = true;
for(int i = 0; i <= n + 1; i++) dis[i][a][b] = inf;
dis[0][a][b] = 0;
priority_queue < pii, vector< pii >, greater < pii > > pq;
pq.push({0, 0});
while(!pq.empty())
{
ll x = pq.top().s, d = pq.top().f;
pq.pop();
if(d > dis[x][a][b]) continue;
for(auto v: grafo[x])
{
if(dis[v.f][a][b] > dis[x][a][b] + v.s)
{
dis[v.f][a][b] = dis[x][a][b] + v.s;
pq.push({dis[v.f][a][b], v.f});
}
}
}
return dis[n + 1][a][b];
}
inline void dijkstra3(int a, int b)
{
if(calc[a][b]) return;
calc[a][b] = true;
for(int i = 0; i <= n + 1; i++) dis2[i][a][b] = inf;
dis2[n + 1][a][b] = 0;
priority_queue < pii, vector< pii >, greater < pii > > pq;
pq.push({0, n + 1});
while(!pq.empty())
{
ll x = pq.top().s, d = pq.top().f;
pq.pop();
if(d > dis2[x][a][b]) continue;
for(auto v: grafo[x])
{
if(dis2[v.f][a][b] > dis2[x][a][b] + v.s)
{
dis2[v.f][a][b] = dis2[x][a][b] + v.s;
pq.push({dis2[v.f][a][b], v.f});
}
}
}
}
inline 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(a, b));
for(int i = 1; i <= n; i++)
{
grafo[i].pop_back();
grafo[i].pop_back();
grafo[0].pop_back();
grafo[n + 1].pop_back();
}
}
inline 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(a, b); dijkstra3(a, b);
for(int i = 1; i <= n; i++) ans = min(ans, dis[i][a][b] + dis2[i][a][b] + 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:239:12: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
int c, d;
^
cities.cpp:239:9: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
int c, d;
^
cities.cpp:213:13: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
int c, d;
^
cities.cpp:222: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 |
6 ms |
4984 KB |
Output is correct |
| 2 |
Correct |
8 ms |
5228 KB |
Output is correct |
| 3 |
Correct |
8 ms |
5228 KB |
Output is correct |
| 4 |
Correct |
8 ms |
5228 KB |
Output is correct |
| 5 |
Incorrect |
6 ms |
5248 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1739 ms |
25784 KB |
Output is correct |
| 2 |
Correct |
481 ms |
26692 KB |
Output is correct |
| 3 |
Correct |
285 ms |
26692 KB |
Output is correct |
| 4 |
Correct |
94 ms |
26692 KB |
Output is correct |
| 5 |
Correct |
1192 ms |
26692 KB |
Output is correct |
| 6 |
Correct |
88 ms |
26692 KB |
Output is correct |
| 7 |
Correct |
10 ms |
26692 KB |
Output is correct |
| 8 |
Correct |
9 ms |
26692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
26692 KB |
Output is correct |
| 2 |
Correct |
11 ms |
26692 KB |
Output is correct |
| 3 |
Correct |
11 ms |
26692 KB |
Output is correct |
| 4 |
Correct |
8 ms |
26692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3825 ms |
65380 KB |
Output is correct |
| 2 |
Correct |
1542 ms |
66484 KB |
Output is correct |
| 3 |
Correct |
3951 ms |
66484 KB |
Output is correct |
| 4 |
Correct |
2067 ms |
66484 KB |
Output is correct |
| 5 |
Correct |
289 ms |
66484 KB |
Output is correct |
| 6 |
Correct |
122 ms |
66484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6090 ms |
95904 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
