oj.uz

Submission #648453

# Submission time Handle Problem Language Result Execution time Memory
648453 2022-10-06T15:00:45 Z ymm Cities (BOI16_cities) C++17
0 / 100
 139 ms 42156 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'010;
const ll inf = 1e17;
const int K = 5;
ll dis[1<<K][N];
vector<pll> A[N];
int imp[K];
int n, k, m;

void relax(int msk, int v, ll d, set<tuple<ll,ll,ll>> &s)
{
	for (auto [u, w] : A[v]) Loop (msk2, 0, 1<<k) {
		if (d+w + dis[msk2][u] < dis[msk|msk2][u]) {
			s.erase( {dis[msk|msk2][u], msk2, u});
			dis[msk|msk2][u] = d+w + dis[msk2][u];
			s.insert({dis[msk|msk2][u], msk2, u});
		}
	}
}

void dij()
{
	set<tuple<ll,ll,ll>> s;
	Loop (v,0,n)
		dis[0][v] = 0;
	Loop (msk,1,1<<k) Loop (v,0,n)
		dis[msk][v] = inf;
	Loop (i,0,k) {
		s.insert({0, 1<<i, imp[i]});
		dis[1<<i][imp[i]] = 0;
	}
	while (s.size()) {
		auto [d, msk, v] = *s.begin();
		s.erase(s.begin());
		relax(msk, v, d, s);
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> k >> m;
	Loop (i,0,k) {
		cin >> imp[i];
		--imp[i];
	}
	Loop (i,0,m) {
		ll v, u, w;
		cin >> v >> u >> w;
		--v; --u;
		A[v].push_back({u, w});
		A[u].push_back({v, w});
	}
	dij();
	ll ans = inf;
	Loop (v,0,n)
		ans = min(ans, dis[(1<<k)-1][v]);
	cout << ans << '\n';
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 128 ms 23552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 129 ms 29640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 42156 KB Output isn't correct
2 Halted 0 ms 0 KB -