oj.uz

Submission #56425

# Submission time Handle Problem Language Result Execution time Memory
56425 2018-07-11T09:28:58 Z win11905 Cities (BOI16_cities) C++11
100 / 100
 3435 ms 124328 KB 
#include <bits/stdc++.h>
#define long long long
#define pll pair<long, long>
#define x first
#define y second
using namespace std;

const int N = 2e5+5;
long INF = 1e18;

int n, k, m;
long d[1<<5][N];
vector<pll> g[N];

void dijkstra(long d[]) {
    priority_queue<pll, vector<pll>, greater<pll> > Q;
    for(int i = 1; i <= n; ++i) Q.emplace(d[i], i);
    while(!Q.empty()) {
        auto now = Q.top(); Q.pop();
        if(now.x != d[now.y]) continue;
        for(auto v : g[now.y]) if(d[v.x] > now.x + v.y)
            Q.emplace(d[v.x] = now.x + v.y, v.x);
    }
}

int main() {
    scanf("%d %d %d", &n, &k, &m);
    fill_n(d[0], N * (1<<5), INF);
    for(int i = 0, a; i < k; ++i) {
        scanf("%d", &a);
        d[1<<i][a] = 0; 
    }
    for(int i = 0, u, v, w; i < m; ++i) {
        scanf("%d %d %d", &u, &v, &w);
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    for(int i = 1; i < (1<<k); ++i) {
        for(int j = i; j; j = (j - 1) & i) {
            int v = i - j;
            for(int z = 1; z <= n; ++z) d[i][z] = min(d[i][z], d[j][z] + d[v][z]);
        }
        dijkstra(d[i]);
    } 
    printf("%lld\n", *min_element(d[(1<<k)-1], d[(1<<k)-1] + N));
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &k, &m);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a);
         ~~~~~^~~~~~~~~~
cities.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &u, &v, &w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 55160 KB Output is correct
2 Correct 45 ms 55252 KB Output is correct
3 Correct 46 ms 55252 KB Output is correct
4 Correct 49 ms 55252 KB Output is correct
5 Correct 49 ms 55252 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 819 ms 72244 KB Output is correct
2 Correct 889 ms 76100 KB Output is correct
3 Correct 623 ms 76100 KB Output is correct
4 Correct 162 ms 76100 KB Output is correct
5 Correct 532 ms 86504 KB Output is correct
6 Correct 179 ms 86504 KB Output is correct
7 Correct 45 ms 86504 KB Output is correct
8 Correct 43 ms 86504 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 86504 KB Output is correct
2 Correct 46 ms 86504 KB Output is correct
3 Correct 44 ms 86504 KB Output is correct
4 Correct 45 ms 86504 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1962 ms 90316 KB Output is correct
2 Correct 1804 ms 94048 KB Output is correct
3 Correct 1287 ms 94048 KB Output is correct
4 Correct 1063 ms 97988 KB Output is correct
5 Correct 307 ms 98156 KB Output is correct
6 Correct 216 ms 102340 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3435 ms 108264 KB Output is correct
2 Correct 3276 ms 112432 KB Output is correct
3 Correct 3025 ms 116128 KB Output is correct
4 Correct 2437 ms 116128 KB Output is correct
5 Correct 1717 ms 120188 KB Output is correct
6 Correct 418 ms 120360 KB Output is correct
7 Correct 167 ms 124328 KB Output is correct