oj.uz

Submission #969725

# Submission time Handle Problem Language Result Execution time Memory
969725 2024-04-25T13:49:59 Z momo50 Cities (BOI16_cities) C++14
100 / 100
 3198 ms 75772 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dist[100007][1<<6];
bool vis[100007][1<<6];
vector<pair<int,ll>> g[100007];
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;

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

    int n,k,m,a;
    cin>>n>>k>>m;

    for(int i=1;i<=n;i++)
        for(int j=0;j<(1<<k);j++)
            dist[i][j]=1e17+7;
    for(int i=0;i<k;i++)
    {
        int a;
        cin>>a;
        dist[a][1<<i]=0;
    }
    for(int i=0;i<m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        g[u].emplace_back(v,w);
        g[v].emplace_back(u,w);
    }


    for(int mask=1;mask<(1<<k);mask++)
    {
        for(int i=0;i<k;i++)
        {
            int thisM=1<<i;
            if(!(thisM&mask))continue;
            int Nothis=(mask^thisM);
            for(int j=1;j<=n;j++)
                dist[j][mask]=min(dist[j][mask],dist[j][thisM]+dist[j][Nothis]);
        }
        for(int i=1;i<=n;i++)
        {
            pq.emplace(dist[i][mask],i);
        }
        while(!pq.empty())
        {
            int u,v,w;
            u=pq.top().second;
            pq.pop();
            for(auto& [v,w]:g[u])
            {
                if(dist[v][mask]>dist[u][mask]+w)
                {
                    dist[v][mask]=dist[u][mask]+w;
                    pq.emplace(dist[v][mask],v);
                }
            }
        }
    }


    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:53:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |             for(auto& [v,w]:g[u])
      |                       ^
cities.cpp:50:19: warning: unused variable 'v' [-Wunused-variable]
   50 |             int u,v,w;
      |                   ^
cities.cpp:50:21: warning: unused variable 'w' [-Wunused-variable]
   50 |             int u,v,w;
      |                     ^
cities.cpp:13:15: warning: unused variable 'a' [-Wunused-variable]
   13 |     int n,k,m,a;
      |               ^

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 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 2 ms 6744 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 772 ms 74716 KB Output is correct
2 Correct 735 ms 73592 KB Output is correct
3 Correct 488 ms 64456 KB Output is correct
4 Correct 63 ms 19308 KB Output is correct
5 Correct 381 ms 75248 KB Output is correct
6 Correct 53 ms 19024 KB Output is correct
7 Correct 4 ms 7004 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1606 ms 75592 KB Output is correct
2 Correct 1475 ms 73688 KB Output is correct
3 Correct 939 ms 64412 KB Output is correct
4 Correct 909 ms 48404 KB Output is correct
5 Correct 192 ms 24816 KB Output is correct
6 Correct 79 ms 21320 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3198 ms 75772 KB Output is correct
2 Correct 3007 ms 74184 KB Output is correct
3 Correct 2998 ms 73684 KB Output is correct
4 Correct 2037 ms 64456 KB Output is correct
5 Correct 1719 ms 48068 KB Output is correct
6 Correct 256 ms 24756 KB Output is correct
7 Correct 99 ms 21708 KB Output is correct