Submission #485706

#	Time	Username	Problem	Language	Result	Execution time	Memory
485706		duchung	Cities (BOI16_cities)	C++17	100 / 100	2906 ms	48896 KiB

cities

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int , int>
const int INF = 1e18;
const int N = 1e5 + 5;
const int K = 5;

int n , k , m;
vector<ii> edge[N];
int dist[N][1 << K];

void dijkstra(int mask)
{
    priority_queue<ii , vector<ii> , greater<ii>> q;
    for (int i = 1 ; i <= n ; ++i) q.push({dist[i][mask] , i});
    
    while(!q.empty())
    {
        int d = q.top().first;
        int u = q.top().second;
        q.pop();
        
        if (dist[u][mask] != d) continue;
        
        for (auto adj : edge[u])
        {
            int v = adj.first;
            int w = adj.second;
            if (dist[v][mask] > dist[u][mask] + w)
            {
                dist[v][mask] = dist[u][mask] + w;
                q.push({dist[v][mask] , v});
            }
        }
        
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> k >> m;
    
    for (int mask = 0 ; mask < (1 << k) ; ++mask)
    {
        for (int i = 1 ; i <= n ; ++i)
        {
            dist[i][mask] = INF;
        }
    }
    
    for (int i = 1 ; i <= k ; ++i)
    {
        int tmp;
        cin >> tmp;
        dist[tmp][1 << (i - 1)] = 0; 
    }
    
    for (int i = 1 ; i <= m ; ++i)
    {
        int u , v , w;
        cin >> u >> v >> w;
        edge[u].push_back({v , w});
        edge[v].push_back({u , w});
    }
    
    for (int mask = 1 ; mask < (1 << k) ; ++mask)
    {
        for (int sub = mask ; sub >= 1 ; sub = (sub - 1) & mask)
        {
            for (int i = 1 ; i <= n ; ++i)
            {
                dist[i][mask] = min(dist[i][mask] , dist[i][sub] + dist[i][mask ^ sub]);
            }
        }
        dijkstra(mask);
    }
    
    int ans = INF;
    for (int i = 1 ; i <= n ; ++i) ans = min(ans , dist[i][(1 << k) - 1]);
    cout << ans;
}

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