Submission #1027908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027908		hasan2006	Cities (BOI16_cities)	C++17	100 / 100	1739 ms	54856 KiB

cities

#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 (stderr)

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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26