#include <bits/stdc++.h>
using namespace std;
#define int long long
int inf = 1e18;
int n,k,m;
vector<int> imp;
vector<pair<int,int>> g[200005];
int dp[200005][16];
vector<int> d[5];
vector<int> dijkstra(int nod0)
{
vector<int> dist(n + 1);
for (int i = 1; i <= n; i++)
dist[i] = inf;
priority_queue<pair<int,int>> pq;
pq.push({0,nod0});
while (!pq.empty())
{
int nod = pq.top().second,cost = -pq.top().first;
pq.pop();
if (dist[nod] == inf)
{
dist[nod] = cost;
for (auto vecin : g[nod])
{
pq.push({-(vecin.second + cost),vecin.first});
}
}
}
return dist;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> k >> m;
for (int i = 1; i <= k; i++)
{
int x;
cin >> x;
imp.push_back(x);
}
sort(imp.begin(),imp.end());
for (int i = 0; i < imp.size() - 1; i++)
if (imp[i] == imp[i + 1])
assert(false);
shuffle(imp.begin(),imp.end(),default_random_engine(676));
for (int i = 1; i <= m; i++)
{
int x,y,z;
cin >> x >> y >> z;
g[x].push_back({y,z});
g[y].push_back({x,z});
}
k--;
for (int i = 0; i <= k; i++)
d[i] = dijkstra(imp[i]);
for (int mask = 1; mask < (1 << k); mask++)
{
for (int nod = 1; nod <= n; nod++)
{
dp[nod][mask] = inf;
for (int mask2 = 1; mask2 <= mask; mask2++)
{
if ((mask & mask2) != mask2)
continue;
int lft = 0;
for (int bit = 0; bit < k; bit++)
{
if ((1 << bit) & mask2)
lft += d[bit][nod];
}
dp[nod][mask] = min(dp[nod][mask],dp[nod][mask - mask2] + lft);
}
}
for (int nod = 1; nod <= n; nod++)
{
vector<vector<int>> dpp;
dpp.resize(g[nod].size());
for (int i = 0; i < g[nod].size(); i++)
dpp[i].resize((1 << k));
for (int i = 0; i < g[nod].size(); i++)
for (int j = 0; j < (1 << k); j++)
dpp[i][j] = inf;
for (int i = 0; i < g[nod].size(); i++)
{
if (i == 0)
{
for (int j = 0; j < (1 << k); j++)
{
if ((j & mask) != j or (j == mask))
continue;
if (j != 0)
dpp[i][j] = dp[g[nod][0].first][j] + g[nod][0].second;
}
}
else
{
for (int j = 0; j < (1 << k); j++)
{
if ((j & mask) != j)
continue;
dpp[i][j] = dpp[i - 1][j];
if (j != 0)
{
for (int jj = 1; jj < (1 << k); jj++)
{
if ((j & jj) != jj or (jj == mask))
continue;
dpp[i][j] = min(dpp[i][j],dpp[i - 1][j - jj] + g[nod][i].second + dp[g[nod][i].first][jj]);
}
}
}
}
}
dp[nod][mask] = min(dp[nod][mask],dpp[(int)g[nod].size() - 1][mask]);
}
set<pair<int,int>> s;
for (int nod = 1; nod <= n; nod++)
s.insert({dp[nod][mask],nod});
vector<bool> scos(n + 1);
while (!s.empty())
{
pair<int,int> idk = *s.begin();
s.erase(idk);
scos[idk.second] = true;
for (auto it : g[idk.second])
{
if (!scos[it.first])
{
s.erase({dp[it.first][mask],it.first});
int new_cost = min(dp[it.first][mask],idk.first + it.second);
dp[it.first][mask] = new_cost;
s.insert({new_cost,it.first});
}
}
}
}
int ans = dp[imp[k]][(1 << k) - 1];
cout << ans;
return 0;
}
/*
4 2 6
1 3
1 2 4
1 3 9
1 4 6
2 3 2
2 4 5
3 4 8
*/
/**
as vrea sa imi fac un dp[nod][mask] = presupunand ca am plecat din imp[0] si am drum spre nod, cat imi mai ia ca sa ma conectez cu nod de mask
1.dp[nod][mask] ar putea fi dp[nod][mask2], mask2 inclus in mask cu tranzitia dp[nod][mask2] + sum(dist(nd,nod)) cu nd special in mask - mask2
acum sa presupun ca nu leg nodul nod de cnv in mod direct
2.dp[nod][mask] ar putea fi sum(dp[vec][mask_vec] + cost_edge_nod_vec) cu reuniune(mask_vec) = mask, mask_vec disjuncte (caz pe care iau macar 2 vecini)
3.dp[nod][mask] = cost_edge_nod_vec + dp[vec][mask], pe care ordinea in care calculez e gen dupa dp-uri inainte de a lua cazul asta
Complexitate: O(intra in timp)
**/
Compilation message
cities.cpp: In function 'int main()':
cities.cpp:51:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for (int i = 0; i < imp.size() - 1; i++)
| ~~^~~~~~~~~~~~~~~~
cities.cpp:87:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for (int i = 0; i < g[nod].size(); i++)
| ~~^~~~~~~~~~~~~~~
cities.cpp:89:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for (int i = 0; i < g[nod].size(); i++)
| ~~^~~~~~~~~~~~~~~
cities.cpp:92:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for (int i = 0; i < g[nod].size(); i++)
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
5212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
5212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
5212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
5208 KB |
Output is correct |
| 5 |
Correct |
2 ms |
5212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
740 ms |
38544 KB |
Output is correct |
| 2 |
Correct |
662 ms |
37704 KB |
Output is correct |
| 3 |
Correct |
264 ms |
33920 KB |
Output is correct |
| 4 |
Correct |
377 ms |
30320 KB |
Output is correct |
| 5 |
Correct |
340 ms |
37652 KB |
Output is correct |
| 6 |
Correct |
196 ms |
28956 KB |
Output is correct |
| 7 |
Correct |
5 ms |
5720 KB |
Output is correct |
| 8 |
Correct |
3 ms |
5464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
5724 KB |
Output is correct |
| 2 |
Correct |
8 ms |
5724 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5468 KB |
Output is correct |
| 4 |
Correct |
7 ms |
5724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1481 ms |
39124 KB |
Output is correct |
| 2 |
Correct |
1489 ms |
38532 KB |
Output is correct |
| 3 |
Correct |
575 ms |
34520 KB |
Output is correct |
| 4 |
Correct |
1083 ms |
26144 KB |
Output is correct |
| 5 |
Correct |
851 ms |
29800 KB |
Output is correct |
| 6 |
Correct |
633 ms |
32928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3186 ms |
39908 KB |
Output is correct |
| 2 |
Correct |
3278 ms |
39916 KB |
Output is correct |
| 3 |
Correct |
3192 ms |
39408 KB |
Output is correct |
| 4 |
Incorrect |
1230 ms |
35152 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
