oj.uz

Submission #84876

# Submission time Handle Problem Language Result Execution time Memory
84876 2018-11-17T16:39:09 Z atoiz Cities (BOI16_cities) C++14
100 / 100
 2753 ms 42612 KB 
#pragma GCC optimize ("Ofast")

#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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2840 KB Output is correct
3 Correct 4 ms 2872 KB Output is correct
4 Correct 4 ms 3048 KB Output is correct
5 Correct 5 ms 3076 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 721 ms 23736 KB Output is correct
2 Correct 710 ms 23736 KB Output is correct
3 Correct 453 ms 23736 KB Output is correct
4 Correct 103 ms 23736 KB Output is correct
5 Correct 394 ms 23736 KB Output is correct
6 Correct 152 ms 23736 KB Output is correct
7 Correct 7 ms 23736 KB Output is correct
8 Correct 6 ms 23736 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1434 ms 30104 KB Output is correct
2 Correct 1390 ms 30104 KB Output is correct
3 Correct 982 ms 30104 KB Output is correct
4 Correct 800 ms 30104 KB Output is correct
5 Correct 263 ms 30104 KB Output is correct
6 Correct 95 ms 30104 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2753 ms 42612 KB Output is correct
2 Correct 2624 ms 42612 KB Output is correct
3 Correct 2580 ms 42612 KB Output is correct
4 Correct 1875 ms 42612 KB Output is correct
5 Correct 1373 ms 42612 KB Output is correct
6 Correct 346 ms 42612 KB Output is correct
7 Correct 127 ms 42612 KB Output is correct