Submission #1222566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222566		minhpk	Cities (BOI16_cities)	C++20	52 / 100	6095 ms	120988 KiB

cities

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b,c;
int t[10000];
vector <pair<int,int>> z[1000005];
int cnt[100005][27];
int bruh=1e18;
struct node{
     int val,x,mask;
};
void dijkstra(){
    for (int i=1;i<=a;i++){
        for (int j=0;j<(1<<b);j++){
             cnt[i][j]=bruh;
        }
    }
    for (int i=0;i<b;i++){
         cnt[t[i]][1<<i]=0;
    }
    for (int mask=0;mask<1<<b;mask++){
        priority_queue<pair<int,int> ,vector<pair<int,int>> ,greater<pair<int,int>>> q;
       for (int i=1;i<=a;i++){
        for (int submask=mask;submask>0;submask=(submask-1)&mask){
             cnt[i][mask]=min(cnt[i][mask],cnt[i][submask]+cnt[i][mask^submask]);
             if (cnt[i][mask]!=bruh){
                 q.push({cnt[i][mask],i});
             }
        }

       }
        while (q.size()){
         pair<int,int> pos=q.top();
         q.pop();
         int val=pos.first;
         int pos1=pos.second;
         if (val>cnt[pos1][mask]){
             continue;
         }
         for (auto p:z[pos1]){
              if (cnt[p.first][mask]>val+p.second){
                  cnt[p.first][mask]=val+p.second;
                  q.push({cnt[p.first][mask],p.first});
              }
         }
        }
    }

    int res=bruh;
    for (int i=1;i<=a;i++){
         res=min(res,cnt[i][(1<<b) -1]);
    }
    cout << res << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b >> c;
    for (int i=0;i<b;i++){
         cin >> t[i];
    }
    for (int i=1;i<=c;i++){
         int x,y,t;
         cin >> x >> y >> t;
         z[x].push_back({y,t});
         z[y].push_back({x,t});
    }
    dijkstra();
    return 0;
}

• Subtask 1: 0 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 0 / 26