# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
969155 |
2024-04-24T15:45:13 Z |
vjudge1 |
Cities (BOI16_cities) |
C++17 |
|
4093 ms |
41500 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
const int K = 33;
const long long INF = 1e12;
vector<pair<int,int>> vec[N];
long long dis[N][K] , ans = INF;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n,k,m; cin >> n >> k >> m;
int all = 1<<k;
for (int i=0;i<all;i++) {
for (int j=1;j<=n;j++) {
dis[j][i] = INF;
}
}
for (int i=0;i<k;i++) {
int a; cin >> a;
dis[a][1<<i] = 0;
}
while (m--) {
int u,v,w; cin >> u >> v >> w;
vec[u].push_back({w, v});
vec[v].push_back({w, u});
}
for (int b1=1;b1<all;b1++) {
for (int b2=1;b2<b1;b2<<=1) {
if (b1&b2==0) continue;
for (int i=1;i<=n;i++) {
dis[i][b1] = min(dis[i][b1], dis[i][b2] + dis[i][b1^b2]);
}
}
for (int i=1;i<=n;i++) {
if (dis[i][b1]==INF) continue;
q.push({dis[i][b1], i});
}
while (!q.empty()) {
auto [dist,u] = q.top(); q.pop();
for (auto [w,v]:vec[u]) {
if (dis[v][b1] > dis[u][b1] + w) {
dis[v][b1] = dis[u][b1] + w;
q.push({dis[v][b1], v});
}
}
}
}
for (int i=1;i<=n;i++) ans = min(ans, dis[i][all-1]);
cout << ans;
return 0;
}
Compilation message
cities.cpp: In function 'int main()':
cities.cpp:30:22: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
30 | if (b1&b2==0) continue;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3676 KB |
Output is correct |
2 |
Correct |
1 ms |
3676 KB |
Output is correct |
3 |
Correct |
1 ms |
3676 KB |
Output is correct |
4 |
Correct |
1 ms |
3676 KB |
Output is correct |
5 |
Correct |
1 ms |
3676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1218 ms |
41348 KB |
Output is correct |
2 |
Correct |
519 ms |
40724 KB |
Output is correct |
3 |
Incorrect |
52 ms |
33728 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5980 KB |
Output is correct |
2 |
Correct |
6 ms |
6104 KB |
Output is correct |
3 |
Correct |
5 ms |
5976 KB |
Output is correct |
4 |
Correct |
3 ms |
3932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1977 ms |
41500 KB |
Output is correct |
2 |
Correct |
1103 ms |
40892 KB |
Output is correct |
3 |
Incorrect |
99 ms |
33868 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4088 ms |
41252 KB |
Output is correct |
2 |
Correct |
4093 ms |
41164 KB |
Output is correct |
3 |
Correct |
2307 ms |
40864 KB |
Output is correct |
4 |
Incorrect |
192 ms |
33976 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |