제출 #1010366

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1010366		uyt777443	Cities (BOI16_cities)	C++14	100 / 100	1737 ms	50748 KiB

cities

// https://oj.uz/problem/view/BOI16_cities

#include <iostream>
#include <iomanip>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <vector>
#include <utility>
#include <algorithm>
#include <numeric>
#include <string>
#include <cmath>
#include <random>
#include <sstream>
#include <string.h>
#include <assert.h>
#include <limits.h>
using namespace std;

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

typedef pair<int,int> ii;

const int INF = 1e18;

vector<vector<ii> > adj(100000 + 2);
vector<int> sp;
int dp[100000 + 2][32 + 2];

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, k, m; cin >> n >> k >> m;
	for (int i=1; i<=k; i++) {
		int a; cin >> a; sp.pb(a);
	}
	for (int i=1; i<=m; i++) {
		int a, b, c; cin >> a >> b >> c; adj[a].pb({b, c}); adj[b].pb({a, c});
	}

	for (int i=1; i<=n; i++) for (int j=0; j<=32; j++) dp[i][j] = INF;

	for (int i=0; i<k; i++) 
		dp[sp[i]][(1 << i)] = 0;
	// for (auto i : sp)
  
	for (int mask = 1; mask <= (1 << k) - 1; mask++) {
    	for (int i=0; i<5; i++) {
			if (mask & (1 << i)) {
				for (int j=1; j<=n; j++) 
					dp[j][mask] = min(dp[j][mask], dp[j][mask - (1 << i)] + dp[j][(1 << i)]);
			}
		}
		
		priority_queue<ii, vector<ii>, greater<ii> > pq;
		for (int i=1; i<=n; i++) {
			pq.push({dp[i][mask], i});
		}
		
		while(!pq.empty()) {
			ii cur = pq.top(); pq.pop();
			int des = cur.se, dis = cur.fi;
            if (dp[des][mask] != dis) continue; 
			for (auto nx : adj[des]) {
				int ndes = nx.fi, w = nx.se;
                int nxmask = mask;
				// for (int i=0; i<5; i++) {
				// 	if (ndes == sp[i]) nxmask += (1 << i);
				// }
				if (dp[ndes][nxmask] <= dp[des][mask] + w) continue;
                dp[ndes][nxmask] = dp[des][nxmask] + w;
                pq.push({dp[ndes][nxmask], ndes});
			}
		}
	}

	int ans = INF;
	for (int i=1; i<=n; i++) {
		ans = min(ans, dp[i][(1 << k) - 1]);
	} cout << ans;
	
	return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26