oj.uz

Submission #56159

# Submission time Handle Problem Language Result Execution time Memory
56159 2018-07-10T06:38:11 Z 강태규(#1579) Cities (BOI16_cities) C++11
100 / 100
 3380 ms 40936 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

const llong inf = 1e16;
int n, k, m;
struct _edge {
    int x, c;
    _edge(int x, int c) : x(x), c(c) {}
};

struct node {
    int x;
    llong c;
    node(int x, llong c) : x(x), c(c) {}
    bool operator<(const node &p) const {
        return c > p.c;
    }
};

llong dist[1 << 5][100001];
int imp[5];
vector<_edge> edge[100001];
int main() {
    scanf("%d%d%d", &n, &k, &m);
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < (1 << k); ++j) {
            dist[j][i] = inf;
        }
    }
    for (int i = 0; i < k; ++i) {
        scanf("%d", imp + i);
        dist[1 << i][imp[i]] = 0;
    }
    while (m--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edge[a].emplace_back(b, c);
        edge[b].emplace_back(a, c);
    }
    for (int i = 1; i < (1 << k); ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int p = 0; p < i; ++p) {
                if ((i | p) != i) continue;
                dist[i][j] = min(dist[i][j], dist[p][j] + dist[p ^ i][j]);
            }
        }
        priority_queue<node> pq;
        for (int j = 1; j <= n; ++j) {
            if (dist[i][j] < inf) pq.emplace(j, dist[i][j]);
        }
        
        while (!pq.empty()) {
            node x = pq.top();
            pq.pop();
            if (dist[i][x.x] != x.c) continue;
            for (_edge j : edge[x.x]) {
                llong d = x.c + j.c;
                if (d < dist[i][j.x]) {
                    pq.emplace(j.x, dist[i][j.x] = d);
                }
            }
        }
    }
    
    llong ans = inf;
    for (int i = 1; i <= n; ++i) {
        ans = min(ans, dist[(1 << k) - 1][i]);
    }
    printf("%lld\n", ans);
	return 0;
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:41: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:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", imp + i);
         ~~~~~^~~~~~~~~~~~~~~
cities.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2788 KB Output is correct
3 Correct 4 ms 2864 KB Output is correct
4 Correct 5 ms 2912 KB Output is correct
5 Correct 4 ms 2912 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 785 ms 21936 KB Output is correct
2 Correct 721 ms 21936 KB Output is correct
3 Correct 473 ms 21936 KB Output is correct
4 Correct 148 ms 21936 KB Output is correct
5 Correct 449 ms 21936 KB Output is correct
6 Correct 105 ms 21936 KB Output is correct
7 Correct 8 ms 21936 KB Output is correct
8 Correct 8 ms 21936 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21936 KB Output is correct
2 Correct 13 ms 21936 KB Output is correct
3 Correct 8 ms 21936 KB Output is correct
4 Correct 9 ms 21936 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1655 ms 28264 KB Output is correct
2 Correct 1426 ms 28264 KB Output is correct
3 Correct 921 ms 28264 KB Output is correct
4 Correct 801 ms 28264 KB Output is correct
5 Correct 237 ms 28264 KB Output is correct
6 Correct 113 ms 28264 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3280 ms 40936 KB Output is correct
2 Correct 3380 ms 40936 KB Output is correct
3 Correct 3185 ms 40936 KB Output is correct
4 Correct 2301 ms 40936 KB Output is correct
5 Correct 1606 ms 40936 KB Output is correct
6 Correct 415 ms 40936 KB Output is correct
7 Correct 143 ms 40936 KB Output is correct