oj.uz

Submission #968495

# Submission time Handle Problem Language Result Execution time Memory
968495 2024-04-23T13:47:03 Z Yang8on Cities (BOI16_cities) C++14
52 / 100
 1413 ms 44304 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 = 1; y <= k; y ++) if(gb(x, y - 1))
            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 solve()':
cities.cpp:72:49: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   72 |         for(int y = 1; y <= k; y ++) if(gb(x, y - 1))
      |                                               ~~^~~
cities.cpp:6:25: note: in definition of macro 'gb'
    6 | #define gb(i, j) ((i >> j) & 1)
      |                         ^
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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 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 6 ms 30044 KB Output is correct
5 Incorrect 5 ms 30040 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 44156 KB Output is correct
2 Correct 449 ms 42968 KB Output is correct
3 Correct 215 ms 36920 KB Output is correct
4 Correct 58 ms 34836 KB Output is correct
5 Correct 242 ms 43032 KB Output is correct
6 Correct 46 ms 34808 KB Output is correct
7 Correct 7 ms 30296 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 30296 KB Output is correct
2 Correct 9 ms 30300 KB Output is correct
3 Correct 7 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 897 ms 44304 KB Output is correct
2 Correct 766 ms 44008 KB Output is correct
3 Correct 508 ms 36944 KB Output is correct
4 Correct 430 ms 39528 KB Output is correct
5 Correct 115 ms 36452 KB Output is correct
6 Correct 51 ms 36640 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1413 ms 44160 KB Output isn't correct
2 Halted 0 ms 0 KB -