Submission #1245834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245834		orzngaiha	Cities (BOI16_cities)	C++20	0 / 100	162 ms	30948 KiB

cities

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
const int N = 2e5+5,LOG = 50;
int n,m,k,dp[N][LOG],a[N];
vector<pii> adj[N];
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>k>>m;

    for(int i = 0;i <= n;i++)
    {
        for(int j = 0;j < (1<<k);j++)
            dp[i][j] = 1e9;
    }
    for (int i = 0; i < k; i++)
    {
    cin >> a[i];
    dp[a[i]][1 << i] = 0;
    }
    for(int i = 1;i <= m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        adj[x].push_back({y,z});
        adj[y].push_back({x,z});
    }
    //    while(!pq.empty())
     for (int mask = 0; mask < (1 << k); mask++)
     {
        for (int submask = mask; submask; submask = (submask - 1) & mask)
        {
            if (submask == mask) continue;
            int o = mask ^ submask;
            for (int u = 1; u <= n; u++)
            {
                dp[u][mask] = min(dp[u][mask], dp[u][submask] + dp[u][o]);
            }
        }
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        for (int u = 1; u <= n; u++) {
            if (dp[u][mask] < 1e9)
                pq.emplace(dp[u][mask], u);
        }

        while (!pq.empty()) {
            auto [cost, u] = pq.top(); pq.pop();
            if (dp[u][mask] != cost) continue;

            for (auto [v, w] : adj[u]) {
                if (dp[v][mask] > dp[u][mask] + w) {
                    dp[v][mask] = dp[u][mask] + w;
                    pq.emplace(dp[v][mask], v);
                }
            }
        }
     }
   int ans = 1e9;
   for(int i = 1;i <= n;i++)
   {
        ans = min(ans,dp[i][(1<<k)-1]);
   }
  cout<<ans;
}

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