Submission #968505

#	Time	Username	Problem	Language	Result	Execution time	Memory
968505		Yang8on	Cities (BOI16_cities)	C++14	100 / 100	1666 ms	48452 KiB

cities

#include <bits/stdc++.h>
#define Y8o "Cities"
#define maxn 100005
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
    return uniform_int_distribution<ll> (l, r) (rng);
}
void iof() {
    if(fopen(Y8o".inp", "r"))
    {
        freopen(Y8o".inp", "r", stdin);
//        freopen(Y8o".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);
}
void ctime() {
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}


int n, k, m, a[maxn];
vector<pii> o[maxn];
ll dp[35][maxn];

void dij(ll dp[maxn])
{
    priority_queue<pair<ll, int>> q;
    for(int i = 1; i <= n; i ++) q.push({ -dp[i], i });

    while(q.size())
    {
        ll val = -q.top().first; int u = q.top().second;
        q.pop();
        if(val > dp[u]) continue;

        for(pii x : o[u])
        {
            int v = x.first, w = x.second;
            if(dp[v] > dp[u] + 1ll * w)
            {
                dp[v] = dp[u] + 1ll * w;
                q.push({ -dp[v], v });
            }
        }
    }
}

void solve()
{
    cin >> n >> k >> m;
    for(int i = 1; i <= k; i ++) cin >> a[i];
    for(int i = 1; i <= m; i ++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        o[u].push_back({ v, w });
        o[v].push_back({ u, w });
    }

    memset(dp, 0x3f, sizeof dp);
    for(int i = 1; i <= k; i ++) dp[1 << (i - 1)][a[i]] = 0;

    for(int x = 1; x <= (1 << k) - 1; x ++)
    {
        for(int i = 1; i <= n; i ++)
        {
            for(int y = x; y; y = (y - 1) & x)
                dp[x][i] = min(dp[x][i], dp[x ^ y][i] + dp[y][i]);
        }

        dij(dp[x]);
    }

    ll ans = 1e18;
    for(int i = 1; i <= n; i ++) ans = min(ans, dp[(1 << k) - 1][i]);

    cout << ans;
}


int main()
{
    iof();

    int nTest = 1;
//    cin >> nTest;

    while(nTest --) {
        solve();
    }

    ctime();
    return 0;
}

Compilation message (stderr)

cities.cpp: In function 'void iof()':
cities.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(Y8o".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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