oj.uz

Submission #310326

# Submission time Handle Problem Language Result Execution time Memory
310326 2020-10-06T16:31:32 Z BeanZ Cities (BOI16_cities) C++14
100 / 100
 2606 ms 44992 KB 
// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define endl '\n'
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
ll dp[(1 << 5) + 1][N], p[N];
vector<pair<ll, ll>> node[N];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("A.inp", "r")){
            freopen("test.inp", "r", stdin);
            freopen("test.out", "w", stdout);
    }
    ll n, k, m;
    cin >> n >> k >> m;
    for (int i = 0; i < (1 << k); i++){
        for (int j = 1; j <= n; j++){
            dp[i][j] = 1e18;
        }
    }
    for (int i = 0; i < k; i++) cin >> p[i], dp[(1 << i)][p[i]] = 0;
    for (int i = 1; i <= m; i++){
        ll u, v, c;
        cin >> u >> v >> c;
        node[u].push_back({v, c});
        node[v].push_back({u, c});
    }
    for (int i = 1; i < (1 << k); i++){
        for (int j = 0; j < k; j++){
            if (!(i & (1 << j))) continue;
            ll mask = i ^ (1 << j);
            for (int u = 1; u <= n; u++){
                dp[i][u] = min(dp[i][u], dp[mask][u] + dp[(1 << j)][u]);
            }
        }
        priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
        for (int j = 1; j <= n; j++){
            //cout << dp[i][j]  << i << " " << j << endl;
            pq.push({dp[i][j], j});
        }
        while (pq.size()){
            pair<ll, ll> x = pq.top();
            pq.pop();
            if (x.first != dp[i][x.second]) continue;
            for (auto j : node[x.second]){
                if ((x.first + j.second) < dp[i][j.first]){
                    dp[i][j.first] = x.first + j.second;
                    pq.push({dp[i][j.first], j.first});
                }
            }
        }
    }
    ll ans = 1e18;
    for (int i = 1; i <= n; i++){
        ans = min(ans, dp[(1 << k) - 1][i]);
    }
    cout << ans;
}
/*
*/

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:15:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   15 |             freopen("test.inp", "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:16:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   16 |             freopen("test.out", "w", stdout);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 2 ms 2816 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 730 ms 25948 KB Output is correct
2 Correct 678 ms 25464 KB Output is correct
3 Correct 475 ms 17888 KB Output is correct
4 Correct 79 ms 11768 KB Output is correct
5 Correct 389 ms 22740 KB Output is correct
6 Correct 72 ms 11688 KB Output is correct
7 Correct 5 ms 2944 KB Output is correct
8 Correct 4 ms 2944 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3072 KB Output is correct
2 Correct 7 ms 3072 KB Output is correct
3 Correct 7 ms 2944 KB Output is correct
4 Correct 6 ms 2944 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1366 ms 32220 KB Output is correct
2 Correct 1340 ms 31808 KB Output is correct
3 Correct 885 ms 24152 KB Output is correct
4 Correct 716 ms 23052 KB Output is correct
5 Correct 192 ms 14668 KB Output is correct
6 Correct 92 ms 14288 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2606 ms 44992 KB Output is correct
2 Correct 2553 ms 44636 KB Output is correct
3 Correct 2512 ms 44312 KB Output is correct
4 Correct 1703 ms 37000 KB Output is correct
5 Correct 1315 ms 29584 KB Output is correct
6 Correct 289 ms 16020 KB Output is correct
7 Correct 98 ms 14144 KB Output is correct