oj.uz

Submission #84874

# Submission time Handle Problem Language Result Execution time Memory
84874 2018-11-17T16:38:31 Z atoiz Cities (BOI16_cities) C++14
100 / 100
 2800 ms 70948 KB 
#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 2808 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 4 ms 3032 KB Output is correct
5 Correct 4 ms 3096 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 739 ms 27532 KB Output is correct
2 Correct 717 ms 27532 KB Output is correct
3 Correct 433 ms 27532 KB Output is correct
4 Correct 92 ms 27532 KB Output is correct
5 Correct 388 ms 27532 KB Output is correct
6 Correct 94 ms 27532 KB Output is correct
7 Correct 8 ms 27532 KB Output is correct
8 Correct 6 ms 27532 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1385 ms 37976 KB Output is correct
2 Correct 1328 ms 40436 KB Output is correct
3 Correct 987 ms 40436 KB Output is correct
4 Correct 818 ms 40436 KB Output is correct
5 Correct 258 ms 40436 KB Output is correct
6 Correct 113 ms 40436 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2694 ms 70876 KB Output is correct
2 Correct 2800 ms 70948 KB Output is correct
3 Correct 2713 ms 70948 KB Output is correct
4 Correct 2004 ms 70948 KB Output is correct
5 Correct 1495 ms 70948 KB Output is correct
6 Correct 358 ms 70948 KB Output is correct
7 Correct 121 ms 70948 KB Output is correct