oj.uz

Submission #968517

# Submission time Handle Problem Language Result Execution time Memory
968517 2024-04-23T14:14:25 Z vjudge1 Cities (BOI16_cities) C++17
100 / 100
 1585 ms 44756 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 y = x; y; y = (y - 1) & x) for(int i = 1; i <= n; i ++)
                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 6 ms 30044 KB Output is correct
2 Correct 5 ms 30044 KB Output is correct
3 Correct 5 ms 30044 KB Output is correct
4 Correct 4 ms 30044 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 401 ms 43232 KB Output is correct
2 Correct 383 ms 43312 KB Output is correct
3 Correct 238 ms 36944 KB Output is correct
4 Correct 53 ms 34868 KB Output is correct
5 Correct 204 ms 43520 KB Output is correct
6 Correct 46 ms 34888 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 8 ms 30296 KB Output is correct
2 Correct 10 ms 30516 KB Output is correct
3 Correct 7 ms 30044 KB Output is correct
4 Correct 8 ms 30300 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 789 ms 43812 KB Output is correct
2 Correct 747 ms 43032 KB Output is correct
3 Correct 457 ms 37520 KB Output is correct
4 Correct 426 ms 39804 KB Output is correct
5 Correct 117 ms 36400 KB Output is correct
6 Correct 52 ms 36640 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1576 ms 43336 KB Output is correct
2 Correct 1585 ms 44756 KB Output is correct
3 Correct 1491 ms 43068 KB Output is correct
4 Correct 930 ms 36944 KB Output is correct
5 Correct 773 ms 39560 KB Output is correct
6 Correct 181 ms 36500 KB Output is correct
7 Correct 61 ms 36596 KB Output is correct