oj.uz

답안 #1007740

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1007740 2024-06-25T12:18:09 Z NintsiChkhaidze Cities (BOI16_cities) C++17
100 / 100
 2128 ms 153544 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define s second
#define f first
#define pii pair <int,int>
#define left h*2,l,(l + r)/2
#define right h*2+1,(l + r)/2 + 1,r
using namespace std;
 
const int N = 2e5 + 5;
const ll inf = 1e18;
int arr[N];
ll dist[7][N],dd[34][N],ddd[N];
ll DD[34][N],val[34][N];
vector <pair <int,ll>> v[N];
 
signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
 
    int n,k,m;
    cin>>n>>k>>m;
 
    for (int i = 1; i <= k; i++)
        cin >> arr[i];
 
    for (int i =1; i <= m; i++){
        int a,b; ll c;
        cin>>a>>b>>c;
        v[a].pb({b,c});
        v[b].pb({a,c});
    }
 
	for (int i = 1; i <= k; i++){
		for (int j = 1; j <= n; j++)
			dist[i][j] = inf;
 
		priority_queue<pair <ll,int>> pq;
		dist[i][arr[i]] = 0;
		pq.push({0,arr[i]});
		while (pq.size()){
			ll D = -pq.top().f; int x = pq.top().s;
			pq.pop();
			if (dist[i][x] != D) continue;
 
			for (auto [to,w]: v[x]){
				if (dist[i][to] > D + w){
					dist[i][to] = D + w;
					pq.push({-dist[i][to],to});
				}
			}
		}
	}
    
	ll ans=inf;
	for (int i = 1; i <= n; i++){
		ll cur=0;
		for (int j = 1; j <= k; j++)
			cur += dist[j][i];
		ans=min(ans,cur);
	}
 
	if (k < 4){
		cout<<ans<<endl;
		exit(0);
	}
	
	for (int mask1=0;mask1<(1<<k); mask1++)
		for(int i=1;i<=n;i++)
			DD[mask1][i] = inf;
	
	for (int mask2=0;mask2<(1<<k); mask2++)
		for (int i = 1; i <= n; i++)
			for (int j=0;j<k;j++)
				if (((mask2>>j) & 1)) val[mask2][i] += (dist[j + 1][i]);
 
	for (int mask1 = 0; mask1 < (1<<k); mask1++){
		for (int i = 1; i <= n; i++){
			dd[mask1][i] = 0;
			for (int j = 0; j < k; j++){
				if (((mask1>>j) & 1)) dd[mask1][i] += dist[j + 1][i];
			}
		}
 
		priority_queue <pair <ll,int>> pq;
		for (int i = 1; i <= n; i++)
			pq.push({-dd[mask1][i],i});
 
		while (pq.size()){
			ll D = -pq.top().f; int x = pq.top().s;
			pq.pop();
			if (dd[mask1][x] != D) continue;
 
			for (auto [to,w]: v[x]){
				if (dd[mask1][to] > D + w){
					dd[mask1][to] = D + w;
					pq.push({-dd[mask1][to],to});
				}
			}
		}
		
		for (int mask2 = 0; mask2 < (1<<k); mask2++){
			int y = (mask1 & mask2);
			if (y > 0) continue;
 
			for (int i = 1; i <= n; i++){
				ll kk = dd[mask1][i] + val[mask2][i];
				DD[(mask1 | mask2)][i] = min(DD[(mask1 | mask2)][i],kk);
			}
		}
		
	}
 
	for (int mask1=0;mask1<(1<<k); mask1++){
		for (int i =1 ; i <= n; i++)
			ddd[i] = DD[mask1][i];
 
		priority_queue <pair <ll,int>> pq;
		for (int i = 1; i <= n; i++)
			pq.push({-ddd[i],i});
 
		while (pq.size()){
			ll D = -pq.top().f; int x = pq.top().s;
			pq.pop();
			if (ddd[x] != D) continue;
 
			for (auto [to,w]: v[x]){
				if (ddd[to] > D + w){
					ddd[to] = D + w;
					pq.push({-ddd[to],to});
				}
			}
		}
 
		for (int i = 1; i <= n; i++){
			ddd[i] += (val[(((1<<k) - 1) ^ mask1)][i]);
			ans=min(ans,ddd[i]);
		}
	}
 
	cout<<ans;
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 7 ms 86740 KB Output is correct
5 Correct 10 ms 111452 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 24976 KB Output is correct
2 Correct 134 ms 25528 KB Output is correct
3 Correct 46 ms 18176 KB Output is correct
4 Correct 40 ms 21952 KB Output is correct
5 Correct 103 ms 22896 KB Output is correct
6 Correct 39 ms 19896 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 86876 KB Output is correct
2 Correct 14 ms 86876 KB Output is correct
3 Correct 13 ms 86772 KB Output is correct
4 Correct 11 ms 86876 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1016 ms 108572 KB Output is correct
2 Correct 922 ms 107048 KB Output is correct
3 Correct 718 ms 99800 KB Output is correct
4 Correct 575 ms 102872 KB Output is correct
5 Correct 156 ms 96336 KB Output is correct
6 Correct 60 ms 97872 KB Output is correct

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2128 ms 152688 KB Output is correct
2 Correct 2109 ms 153432 KB Output is correct
3 Correct 1866 ms 153544 KB Output is correct
4 Correct 1472 ms 145760 KB Output is correct
5 Correct 1088 ms 136980 KB Output is correct
6 Correct 267 ms 121980 KB Output is correct
7 Correct 78 ms 119164 KB Output is correct