oj.uz

Submission #1027908

# Submission time Handle Problem Language Result Execution time Memory
1027908 2024-07-19T11:25:17 Z hasan2006 Cities (BOI16_cities) C++17
100 / 100
 1739 ms 54856 KB 
#include <bits/stdc++.h>

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 1e5 + 9 , mod = 1e9 + 7;
ll  dp[N][40] ,  c[N] , d[N] , a[N] , b[N] ,  p[N];
vector<pair<int,int>>v[N];


void solve()
{
    ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
    cin>>n>>k>>m;

    for(i = 0; i < (1 << k); i++)
        for(j = 0; j < n; j++)
            dp[j][i] = 1e18;
    for(i = 1; i <= k; i++)
        cin>>x , dp[x - 1][(1 << (i - 1))] = 0;
    for(i = 1; i <= m; i++){
        cin>>l>>r>>x;
        l-- , r--;
        v[l].pb({r , x});
        v[r].pb({l , x});
    }
    for(i = 1; i  < (1 << k); i++){
        for(j = 1; j < i; j++){
            x = i ^ j;
            if((j | i) != i || x > j)
                continue;
            for(f = 0; f < n; f++)
                dp[f][i] = min(dp[f][i] , dp[f][j] + dp[f][x]);
        }
        priority_queue<pair<ll,int>>q;
        for(j = 0; j < n; j++){
            c[j] = 0;
            if(dp[j][i] < 1e18)
                q.push({-dp[j][i] , j});
        }
        while(!q.empty()){
            x = q.top().second , y = -q.top().first;
            q.pop();
            if(c[x])
                continue;
            c[x] = 1;
            for(auto to : v[x]){
                if(to.se + y < dp[to.fi][i]){
                    dp[to.fi][i] = to.se + y;
                    q.push({-dp[to.fi][i] , to.fi});
                }
            }
        }
    }
    for(i = 0; i < n; i++)
        mn = min(mn , dp[i][(1 << k)  - 1]);
    cout<<mn<<"\n";
}


int main(){
    TL;
    /*#ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif*/
    int t = 1;
//    cin>>t;
    while(t--)
     {
        solve();
     }
}
// Author : حسن

Compilation message

cities.cpp: In function 'void solve()':
cities.cpp:28:12: warning: unused variable 'q' [-Wunused-variable]
   28 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |            ^
cities.cpp:28:38: warning: unused variable 's' [-Wunused-variable]
   28 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                      ^
cities.cpp:28:69: warning: unused variable 'mx' [-Wunused-variable]
   28 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                                     ^~

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 54856 KB Output is correct
2 Correct 362 ms 54760 KB Output is correct
3 Correct 194 ms 46840 KB Output is correct
4 Correct 41 ms 16976 KB Output is correct
5 Correct 216 ms 52540 KB Output is correct
6 Correct 39 ms 15112 KB Output is correct
7 Correct 3 ms 7004 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8796 KB Output is correct
2 Correct 5 ms 7072 KB Output is correct
3 Correct 3 ms 8904 KB Output is correct
4 Correct 3 ms 6804 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 54840 KB Output is correct
2 Correct 859 ms 54740 KB Output is correct
3 Correct 566 ms 46880 KB Output is correct
4 Correct 416 ms 35772 KB Output is correct
5 Correct 108 ms 19388 KB Output is correct
6 Correct 46 ms 16468 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1739 ms 51700 KB Output is correct
2 Correct 1733 ms 51784 KB Output is correct
3 Correct 1713 ms 52228 KB Output is correct
4 Correct 1137 ms 45756 KB Output is correct
5 Correct 845 ms 32176 KB Output is correct
6 Correct 219 ms 17532 KB Output is correct
7 Correct 51 ms 14676 KB Output is correct