oj.uz

답안 #56424

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
56424 2018-07-11T09:25:16 Z win11905 Cities (BOI16_cities) C++11
0 / 100
 1467 ms 82416 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 = 1e9;

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
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 55288 KB Output is correct
2 Correct 41 ms 55380 KB Output is correct
3 Incorrect 48 ms 55400 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 514 ms 73772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 73772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 835 ms 78052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1467 ms 82416 KB Output isn't correct
2 Halted 0 ms 0 KB -