oj.uz

Submission #968505

# Submission time Handle Problem Language Result Execution time Memory
968505 2024-04-23T13:59:32 Z Yang8on Cities (BOI16_cities) C++14
100 / 100
 1666 ms 48452 KB 
#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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 30044 KB Output is correct
2 Correct 5 ms 30044 KB Output is correct
3 Correct 5 ms 30040 KB Output is correct
4 Correct 6 ms 30040 KB Output is correct
5 Correct 5 ms 30044 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 44664 KB Output is correct
2 Correct 413 ms 42952 KB Output is correct
3 Correct 238 ms 36936 KB Output is correct
4 Correct 46 ms 34808 KB Output is correct
5 Correct 218 ms 44172 KB Output is correct
6 Correct 45 ms 34804 KB Output is correct
7 Correct 7 ms 30300 KB Output is correct
8 Correct 6 ms 30300 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 30300 KB Output is correct
2 Correct 8 ms 30248 KB Output is correct
3 Correct 8 ms 30044 KB Output is correct
4 Correct 7 ms 30300 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 733 ms 42848 KB Output is correct
2 Correct 760 ms 43132 KB Output is correct
3 Correct 505 ms 37724 KB Output is correct
4 Correct 446 ms 40048 KB Output is correct
5 Correct 138 ms 36580 KB Output is correct
6 Correct 52 ms 36648 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1666 ms 44728 KB Output is correct
2 Correct 1639 ms 47628 KB Output is correct
3 Correct 1583 ms 48452 KB Output is correct
4 Correct 989 ms 39064 KB Output is correct
5 Correct 848 ms 43860 KB Output is correct
6 Correct 180 ms 40356 KB Output is correct
7 Correct 66 ms 40032 KB Output is correct