Submission #969139

#	Time	Username	Problem	Language	Result	Execution time	Memory
969139		vjudge1	Cities (BOI16_cities)	C++17	0 / 100	203 ms	262144 KiB

cities

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dist[100007][1<<6];
bool vis[100007][1<<6];
map<int,int> mp;
vector<int> re(7);
vector<tuple<int,ll,int>> g[100007];
priority_queue<tuple<ll,int,int,vector<bool>>,vector<tuple<ll,int,int,vector<bool>>>,greater<tuple<ll,int,int,vector<bool>>>> pq;

int main()
{
    cin.tie(nullptr)->ios::sync_with_stdio(false);

    int n,k,m,a;
    cin>>n>>k>>m;
    for(int i=0;i<k;i++)
    {
        cin>>re[i];
        mp[re[i]]=1<<i;
    }
    for(int i=0;i<m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w,i});
        g[v].push_back({u,w,i});
    }

    for(int i=1;i<=n;i++)
        for(int j=0;j<(1<<k);j++)
            dist[i][j]=1e18+7;

    vector<bool> tmp(n+1,0);
    dist[re[0]][1]=0;
    pq.push({0,re[0],1,tmp});
    while(!pq.empty())
    {
        int u,v,w,bit,idx;
        tie(ignore,u,bit,tmp)=pq.top();
        //cout<<u<<" "<<bit<<" "<<dist[u][bit]<<"\n";
        pq.pop();
        vis[u][bit]=true;
        for(auto vw:g[u])
        {
            tie(v,w,idx)=vw;
            int mask=bit|mp[v];
            if(vis[v][mask])continue;
            if(tmp[idx])w=0;
            if(dist[v][mask]>dist[u][bit]+w)
            {
                //cout<<v<<" "<<mask<<"\n";
                bool tmp2=tmp[idx];
                tmp[idx]=true;
                dist[v][mask]=dist[u][bit]+w;
                pq.push({dist[v][mask],v,mask,tmp});
                if(!tmp2)tmp[idx]=false;
            }
        }
    }

    ll ans=LLONG_MAX;
    for(int i=1;i<=n;i++)
    {
        ans=min(ans,dist[i][(1<<k)-1]);
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:15:15: warning: unused variable 'a' [-Wunused-variable]
   15 |     int n,k,m,a;
      |               ^

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