Submission #27721

#	Time	Username	Problem	Language	Result	Execution time	Memory
27721		zoomswk	Cities (BOI16_cities)	C++14	100 / 100	2849 ms	41828 KiB

cities

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

vector<pair<int, int>> way[100005];
int gg[10];
long long dist[32][100005];
priority_queue<pair<long long, int>> pq; // {-dist, pos}
int bit[10];
int orr[35][35];

vector<int> now;

int main(){
    int n, k, m;
    scanf("%d%d%d", &n, &k, &m);
    for(int i=0; i<k; i++) scanf("%d", &gg[i]);
    for(int i=0; i<m; i++){
        int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        way[u].push_back({v, c});
        way[v].push_back({u, c});
    }
    for(int i=0; i<=k; i++) bit[i] = (1<<i);
    for(int i=1; i<(1<<k); i++) for(int j=1; j<=n; j++) dist[i][j] = 1e18;
    for(int i=0; i<k; i++) dist[bit[i]][gg[i]] = 0;
    for(int i=0; i<35; i++) for(int j=0; j<35; j++) orr[i][j] = (i|j);

    for(int mask=1; mask<=bit[k]-1; mask++){
        for(int from=1; from<mask; from++){
            if((from|mask) > mask) continue;
            int other = from^mask;
            for(int i=1; i<=n; i++){
                dist[mask][i] = min(dist[mask][i], dist[from][i]+dist[other][i]);
            }
        }
        for(int i=1; i<=n; i++) pq.push({-dist[mask][i], i});
        while(!pq.empty()){
            long long cur_dist = -pq.top().first;
            int pos = pq.top().second;
            pq.pop();
            if(dist[mask][pos] < cur_dist) continue;
            for(pair<int, int> v : way[pos]){
                if(dist[mask][v.first] > cur_dist+v.second){
                    dist[mask][v.first] = cur_dist+v.second;
                    pq.push({-dist[mask][v.first], v.first});
                }
            }
        }
    }
    long long res = 1e18;
    for(int i=1; i<=n; i++) res = min(res, dist[bit[k]-1][i]);
    printf("%lld", res);
    return 0;
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:15:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &k, &m);
                                ^
cities.cpp:16:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0; i<k; i++) scanf("%d", &gg[i]);
                                               ^
cities.cpp:19:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &u, &v, &c);
                                    ^

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