Submission #637491

#	Time	Username	Problem	Language	Result	Execution time	Memory
637491		minhcool	Cities (BOI16_cities)	C++17	0 / 100	2 ms	596 KiB

cities

//#include "ramen.h"
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 100 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n, m, k;

int dp[128][N], dist[N][N];

void process(){
    cin >> n >> m >> k;
    assert(m <= 20);
    //assert(k > 3 && n > 10);
    for(int i = 0; i < (1LL << k); i++){
        for(int j = 1; j <= n; j++) dp[i][j] = oo;
    }
    for(int i = 1; i <= k; i++){
        int x;
        cin >> x;
        dp[(1LL << (i - 1))][x] = 0;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++) dist[i][j] = (i == j ? 0 : oo);
    }
    for(int i = 1; i <= m; i++){
        int u, v, c;
        cin >> u >> v >> c;
        dist[u][v] = dist[v][u] = min(dist[u][v], c);
    }
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
    /*
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++) cout << i << " " << j << " " << dist[i][j] << "\n";
    }*/
    for(int msk = 1; msk < (1LL << k); msk++){
        if(__builtin_popcountll(msk) < 2) continue;
        for(int root = 1; root <= n; root++){
            for(int sub = msk - 1; sub; sub = (sub - 1) & msk){
            	//cout << root << " " << msk << " " << sub << "\n";
                int mn1 = oo, mn2 = oo;
                for(int root1 = 1; root1 <= n; root1++) mn1 = min(mn1, dp[sub][root1] + dist[root1][root]);
                for(int root2 = 1; root2 <= n; root2++) mn2 = min(mn2, dp[msk ^ sub][root2] + dist[root2][root]);
                //cout << mn1 << " " << mn2 << "\n";
                dp[msk][root] = min(dp[msk][root], mn1 + mn2);
            }
            //cout << msk << " " << root << " " << dp[msk][root] << "\n";
        }
        for(int root = 1; root <= n; root++){
            for(int root2 = 1; root2 <= n; root2++) dp[msk][root] = min(dp[msk][root], dp[msk][root2] + dist[root2][root]);
        }
    }
    int answer = oo;
    for(int i = 1; i <= n; i++) answer = min(answer, dp[(1LL << k) - 1][i]);
    cout << answer << "\n";
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	//freopen("nkbuild.inp", "r", stdin);
	//freopen("nkbuild.out", "w", stdout);
	process();
}

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