oj.uz

Submission #485706

# Submission time Handle Problem Language Result Execution time Memory
485706 2021-11-09T03:45:52 Z duchung Cities (BOI16_cities) C++17
100 / 100
 2906 ms 48896 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 1 ms 2664 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 707 ms 48760 KB Output is correct
2 Correct 696 ms 48440 KB Output is correct
3 Correct 452 ms 38700 KB Output is correct
4 Correct 59 ms 15428 KB Output is correct
5 Correct 337 ms 48700 KB Output is correct
6 Correct 53 ms 15344 KB Output is correct
7 Correct 4 ms 3020 KB Output is correct
8 Correct 4 ms 3020 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3020 KB Output is correct
2 Correct 8 ms 3020 KB Output is correct
3 Correct 4 ms 3020 KB Output is correct
4 Correct 4 ms 2892 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1334 ms 48828 KB Output is correct
2 Correct 1348 ms 48240 KB Output is correct
3 Correct 894 ms 38752 KB Output is correct
4 Correct 724 ms 33592 KB Output is correct
5 Correct 156 ms 19500 KB Output is correct
6 Correct 79 ms 17596 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2906 ms 48808 KB Output is correct
2 Correct 2822 ms 48896 KB Output is correct
3 Correct 2867 ms 48308 KB Output is correct
4 Correct 2032 ms 38904 KB Output is correct
5 Correct 1472 ms 33592 KB Output is correct
6 Correct 238 ms 19488 KB Output is correct
7 Correct 80 ms 17760 KB Output is correct