oj.uz

Submission #969139

# Submission time Handle Problem Language Result Execution time Memory
969139 2024-04-24T15:07:44 Z vjudge1 Cities (BOI16_cities) C++17
0 / 100
 203 ms 262144 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Incorrect 2 ms 6748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 203 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 177 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 182 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -