#include <bits/stdc++.h>
using namespace std;
#define nyahalo ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define otsumiko exit(0);
#define mikodanye priority_queue<pair<long long, long long>, vector<pair<long long, long long> >, greater<pair<long long, long long> > >
#define mikochi priority_queue<long long, vector<long long>, greater<long long> >
long long n, k, m, u, v, c, tl[6], tp[100069], pw[22], pr[100069], ci, ctu, ans = 1e17, cst, dp[100069][4], w, ww, cn, nn, dis[1003][1003], x, y, z;
long long ls[3][4] = {{1, 2, 3, 4}, {1, 3, 2, 4}, {1, 4, 2, 3}};
pair<long long, pair<long long, long long> > ed[100069];
vector<pair<long long, long long> > al[100069];
mikodanye pq;
set<long long> st;
long long fd(long long x) {
if (pr[x] != x) {
pr[x] = fd(pr[x]);
}
return pr[x];
}
int main() {
nyahalo
long long i, j, ii;
pw[0] = 1;
for (i=1; i<=21; i++) {
pw[i] = pw[i-1]*2;
}
cin >> n >> k >> m;
for (i=1; i<=n; i++) {
tp[i] = 0;
pr[i] = i;
dp[i][1] = 1e17;
dp[i][2] = 1e17;
dp[i][3] = 1e17;
}
for (i=1; i<=k; i++) {
cin >> tl[i];
tp[tl[i]] = 1;
}
for (i=1; i<=m; i++) {
cin >> ed[i].second.first >> ed[i].second.second >> ed[i].first;
u = ed[i].second.first;
v = ed[i].second.second;
c = ed[i].first;
al[u].push_back(make_pair(v, c));
al[v].push_back(make_pair(u, c));
}
sort(ed+1, ed+m+1);
if (n<=20 && m<=40) {
for (i=0; i<=pw[n]-1; i++) {
ctu = 0;
for (j=1; j<=k; j++) {
ci = tl[j];
if ((i&pw[ci-1]) == 0) {
ctu = 1;
break;
}
}
if (ctu == 1) {
continue;
}
for (j=1; j<=n; j++) {
pr[j] = j;
}
cst = 0;
for (j=1; j<=m; j++) {
c = ed[j].first;
u = ed[j].second.first;
v = ed[j].second.second;
if ((i&pw[u-1]) == 0 || (i&pw[v-1]) == 0) {
continue;
}
if (fd(u) != fd(v)) {
cst += c;
pr[fd(u)] = fd(v);
}
}
for (j=1; j<=n; j++) {
if ((i&pw[j-1]) == 0) {
continue;
}
st.insert(fd(j));
}
if (st.size()>1) {
cst = 1e17;
}
st.clear();
ans = min(ans, cst);
}
cout << ans << "\n";
otsumiko
}
if (k<=3) {
for (i=1; i<=k; i++) {
for (j=1; j<=n; j++) {
dp[j][i] = 1e17;
}
u = tl[i];
dp[u][i] = 0;
pq.push(make_pair(0, u));
for (; !pq.empty(); ) {
w = pq.top().first;
cn = pq.top().second;
pq.pop();
if (w>dp[cn][i]) {
continue;
}
for (j=0; j<al[cn].size(); j++) {
nn = al[cn][j].first;
ww = al[cn][j].second;
if (dp[nn][i]>dp[cn][i]+ww) {
dp[nn][i] = dp[cn][i]+ww;
pq.push(make_pair(dp[nn][i], nn));
}
}
}
}
if (k == 2) {
v = tl[2];
ans = dp[v][1];
} else {
for (i=1; i<=n; i++) {
//cout << "i: " << i << "\n";
cst = dp[i][1]+dp[i][2]+dp[i][3];
//cout << "cst: " << cst << "\n";
//cout << "dp1: " << dp[i][1] << " dp2: " << dp[i][2] << " dp3: " << dp[i][3] << "\n";
//cout << "\n";
ans = min(ans, cst);
}
}
cout << ans << "\n";
otsumiko
}
if (n<=1000 && m<=2000 && k == 4) {
ans = 1e17;
for (i=1; i<=n; i++) {
for (j=1; j<=n; j++) {
dis[j][i] = 1e17;
}
dis[i][i] = 0;
pq.push(make_pair(0, i));
for (; !pq.empty(); ) {
w = pq.top().first;
cn = pq.top().second;
pq.pop();
if (w>dis[cn][i]) {
continue;
}
for (j=0; j<al[cn].size(); j++) {
nn = al[cn][j].first;
ww = al[cn][j].second;
if (dis[nn][i]>dis[cn][i]+ww) {
dis[nn][i] = dis[cn][i]+ww;
pq.push(make_pair(dis[nn][i], nn));
}
}
}
}
for (i=1; i<=n; i++) {
for (j=i; j<=n; j++) {
for (ii=0; ii<3; ii++) {
x = tl[ls[ii][0]];
y = tl[ls[ii][1]];
z = tl[ls[ii][2]];
w = tl[ls[ii][3]];
cst = dis[x][i]+dis[y][i]+dis[z][j]+dis[w][j]+dis[i][j];
ans = min(ans, cst);
}
}
}
cout << ans << "\n";
otsumiko
}
cout << "sek\n";
otsumiko
}
Compilation message
cities.cpp: In function 'int main()':
cities.cpp:111:20: 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]
111 | for (j=0; j<al[cn].size(); j++) {
| ~^~~~~~~~~~~~~~
cities.cpp:152:20: 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]
152 | for (j=0; j<al[cn].size(); j++) {
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
150 ms |
2764 KB |
Output is correct |
| 3 |
Correct |
84 ms |
2692 KB |
Output is correct |
| 4 |
Correct |
40 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
25 ms |
2644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
264 ms |
23540 KB |
Output is correct |
| 2 |
Correct |
278 ms |
23684 KB |
Output is correct |
| 3 |
Correct |
135 ms |
14960 KB |
Output is correct |
| 4 |
Correct |
77 ms |
16408 KB |
Output is correct |
| 5 |
Correct |
252 ms |
23548 KB |
Output is correct |
| 6 |
Correct |
78 ms |
16408 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2900 KB |
Output is correct |
| 8 |
Correct |
3 ms |
2900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
176 ms |
10768 KB |
Output is correct |
| 2 |
Correct |
176 ms |
10724 KB |
Output is correct |
| 3 |
Incorrect |
61 ms |
10700 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
128 ms |
22332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
127 ms |
22276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
