oj.uz

Submission #968491

# Submission time Handle Problem Language Result Execution time Memory
968491 2024-04-23T13:43:08 Z vjudge1 Cities (BOI16_cities) C++17
52 / 100
 1434 ms 79332 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;
int a[maxn];
vector<pii> o[maxn];
ll dp[31][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:73:49: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   73 |         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 6 ms 27228 KB Output is correct
2 Correct 4 ms 27228 KB Output is correct
3 Correct 4 ms 27228 KB Output is correct
4 Correct 4 ms 27228 KB Output is correct
5 Incorrect 4 ms 27228 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 385 ms 44380 KB Output is correct
2 Correct 407 ms 44564 KB Output is correct
3 Correct 223 ms 36108 KB Output is correct
4 Correct 59 ms 35376 KB Output is correct
5 Correct 217 ms 44728 KB Output is correct
6 Correct 44 ms 35332 KB Output is correct
7 Correct 6 ms 27484 KB Output is correct
8 Correct 5 ms 27392 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 27484 KB Output is correct
2 Correct 8 ms 27484 KB Output is correct
3 Correct 8 ms 27228 KB Output is correct
4 Correct 6 ms 27228 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 45628 KB Output is correct
2 Correct 756 ms 44500 KB Output is correct
3 Correct 481 ms 36208 KB Output is correct
4 Correct 419 ms 40832 KB Output is correct
5 Correct 116 ms 37428 KB Output is correct
6 Correct 66 ms 37200 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 1434 ms 79332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -