oj.uz

답안 #84879

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
84879 2018-11-17T16:42:00 Z atoiz Cities (BOI16_cities) C++14
100 / 100
 2761 ms 42732 KB 
#pragma GCC optimize ("O3")

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <queue>

using namespace std;

#define fi first
#define se second
#define int long long

const int INF = 1e17;
const int MAX = 100100;
int n, k, m;
int spec[5];
vector< pair<int, int> > G[MAX];
priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;

int ans[32][MAX];

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k >> m;
	for (int i = 0; i < k; ++i) cin >> spec[i];
    for (int i = 0; i < m; ++i) {
        int u, v, c; cin >> u >> v >> c;
        G[u].push_back({c, v});
        G[v].push_back({c, u});
    }

    for (int i = 0; i < (1 << k); ++i) {
		for (int j = 1; j <= n; ++j) {
            ans[i][j] = INF;
		}
    }

    for (int i = 0; i < k; ++i) {
        ans[1 << i][spec[i]] = 0;
    }

	for (int mask = 1; mask < (1 << k); ++mask) {
        for (int i = 0; i < k; ++i) if ((mask >> i) & 1) {
			for (int u = 1; u <= n; ++u) {
				ans[mask][u] = min(ans[mask][u], ans[mask ^ (1 << i)][u] + ans[1 << i][u]);
			}
        }

        for (int u = 1; u <= n; ++u) pq.push({ans[mask][u], u});
        while (!pq.empty()) {
            pair<int, int> cur = pq.top(); pq.pop();
            if (ans[mask][cur.se] < cur.fi) continue;
            ans[mask][cur.se] = cur.fi;
            for (pair<int, int> e : G[cur.se]) {
                if (ans[mask][e.se] > cur.fi + e.fi) {
                    ans[mask][e.se] = cur.fi + e.fi;
                    pq.push({ans[mask][e.se], e.se});
                }
            }
        }
	}

	int final_ans = INF;
	for (int u = 1; u <= n; ++u) final_ans = min(final_ans, ans[(1 << k) - 1][u]);
	cout << final_ans;
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2684 KB Output is correct
2 Correct 5 ms 2812 KB Output is correct
3 Correct 5 ms 2880 KB Output is correct
4 Correct 6 ms 2880 KB Output is correct
5 Correct 5 ms 3020 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 752 ms 23684 KB Output is correct
2 Correct 724 ms 23684 KB Output is correct
3 Correct 485 ms 23684 KB Output is correct
4 Correct 116 ms 23684 KB Output is correct
5 Correct 412 ms 23684 KB Output is correct
6 Correct 93 ms 23684 KB Output is correct
7 Correct 7 ms 23684 KB Output is correct
8 Correct 6 ms 23684 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23684 KB Output is correct
2 Correct 10 ms 23684 KB Output is correct
3 Correct 8 ms 23684 KB Output is correct
4 Correct 8 ms 23684 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1340 ms 30072 KB Output is correct
2 Correct 1344 ms 30072 KB Output is correct
3 Correct 931 ms 30072 KB Output is correct
4 Correct 771 ms 30072 KB Output is correct
5 Correct 223 ms 30072 KB Output is correct
6 Correct 100 ms 30072 KB Output is correct

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2761 ms 42732 KB Output is correct
2 Correct 2711 ms 42732 KB Output is correct
3 Correct 2683 ms 42732 KB Output is correct
4 Correct 1957 ms 42732 KB Output is correct
5 Correct 1446 ms 42732 KB Output is correct
6 Correct 707 ms 42732 KB Output is correct
7 Correct 105 ms 42732 KB Output is correct