Submission #1281149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281149		stephit	Cities (BOI16_cities)	C++20	100 / 100	1295 ms	44088 KiB

cities

/*
  __                      
 (_ _|_  _  ._  |_  o _|_ 
 __) |_ (/_ |_) | | |  |_ 
            |             
*/

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define fi first
#define se second
#define endl '\n'
#define debug cout << "NO ERROR", exit(0)
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
const int mod = 1e9 + 7;
const int base = 311;
const int inf = INT_MAX;
const long long inff = LLONG_MAX;
const int d4x[4] = {-1, 1, 0, 0};
const int d4y[4] = {0, 0, 1, -1};
const char c4[4] = {'U', 'D', 'R', 'L'};
const int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

template<class A, class B> bool maximize(A &x, const B &y) { if (x < y) { x = y; return true; } return false; }
template<class A, class B> bool minimize(A &x, const B &y) { if (x > y) { x = y; return true; } return false; }

/*BIGNUM
typedef __int128 BIG;
istream &operator >> (istream &st,BIG &a){string s;a=0;st>>s;bool g=1;for(int i=0;i<s.size();i++){if(i==0&&s[i]=='-'){g=0;continue;}a=a*10+s[i]-'0';}if(!g){a=-a;}return st;}
ostream &operator << (ostream &st,const BIG &a){BIG t=a;if(t==0){st<<0;return st;}if(t<0){st<<'-';t=-t;}string b;while(t!=0){b.push_back((t%10+'0'));t/=10;}reverse(b.begin(),b.end());st<<b;return st;}
//*/

const int N = 2e5 + 5;
int a[5];
using pa = pair<ll, int>;
vector<pa> adj[N];
ll dp[1 << 5][N];

void DoTest() {
    int n, k, m; cin >> n >> k >> m;
    for (int i = 0; i < k; i++) cin >> a[i];

    for (int i = 1; i <= m; i++) {
        int u, v, c; cin >> u >> v >> c;
        adj[u].push_back({c, v});
        adj[v].push_back({c, u});
    }

    // dp[mask][u] là xét đến u và đã đi qua các điểm trong mask

    for (int mask = 1; mask <= (1 << k) - 1; mask++) {
        for (int i = 1; i <= n; i++) dp[mask][i] = 1e17;
    }

    for (int i = 0; i < k; i++) dp[1 << i][a[i]] = 0;

    for (int mask = 1; mask <= (1 << k) - 1; mask++) {
        for (int sub = mask;; sub = (sub - 1) & mask) {
            for (int i = 1; i <= n; i++) {
                int other = mask ^ sub;
                minimize(dp[mask][i], dp[sub][i] + dp[other][i]);
            }
            if (sub == 0) break;
        }

        priority_queue<pa, vector<pa>, greater<pa>> pq;
        for (int i = 1; i <= n; i++) pq.push({dp[mask][i], i});

        while (!pq.empty()) {
            auto [w, i] = pq.top(); pq.pop();
            if (w > dp[mask][i]) continue;

            for (auto [c, j] : adj[i]) {
                if (dp[mask][i] + c >= dp[mask][j]) continue;
                dp[mask][j] = dp[mask][i] + c;
                pq.push({dp[mask][j], j});
            }
        }
    }

    ll ans = inff;
    for (int i = 1; i <= n; i++) minimize(ans, dp[(1 << k) - 1][i]);
    cout << ans;
}

#define file(name)                     \
    freopen(name ".inp", "r", stdin);  \
    freopen(name ".out", "w", stdout); \

signed main() {
    #ifdef ONLINE_JUDGE
       //file("") 
    #endif

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int test = 1;
    //cin >> test;
    for (int _ = 1; _ <= test; _++) DoTest();
}

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