Submission #1010364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010364		uyt777443	Cities (BOI16_cities)	C++17	14 / 100	275 ms	46388 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=1; j<=32; j++) dp[i][j] = INF;

  
	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] = dp[j][mask - (1 << i)] + dp[j][(1 << i)];
			}
		}
		
		priority_queue<ii, vector<ii>, greater<ii> > pq;
        for (int i=0; i<5; i++) {
            if (mask & (1 << i)) {
                dp[sp[i]][(1 << i)] = 0;
                pq.push({dp[sp[i]][mask], sp[i]}); 
            }
        }
		while(!pq.empty()) {
			ii cur = pq.top(); pq.pop();
			int des = cur.se, dis = cur.fi;
			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;
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:67:22: warning: unused variable 'dis' [-Wunused-variable]
   67 |    int des = cur.se, dis = cur.fi;
      |                      ^~~

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