oj.uz

Submission #27721

# Submission time Handle Problem Language Result Execution time Memory
27721 2017-07-13T14:10:51 Z zoomswk Cities (BOI16_cities) C++14
100 / 100
 2849 ms 41828 KB 
#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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 29372 KB Output is correct
2 Correct 0 ms 29372 KB Output is correct
3 Correct 0 ms 29372 KB Output is correct
4 Correct 0 ms 29372 KB Output is correct
5 Correct 0 ms 29372 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 773 ms 41828 KB Output is correct
2 Correct 789 ms 41756 KB Output is correct
3 Correct 356 ms 35652 KB Output is correct
4 Correct 126 ms 33912 KB Output is correct
5 Correct 493 ms 41820 KB Output is correct
6 Correct 116 ms 34000 KB Output is correct
7 Correct 3 ms 29504 KB Output is correct
8 Correct 0 ms 29504 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29504 KB Output is correct
2 Correct 6 ms 29504 KB Output is correct
3 Correct 6 ms 29512 KB Output is correct
4 Correct 3 ms 29504 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1399 ms 41820 KB Output is correct
2 Correct 1109 ms 41612 KB Output is correct
3 Correct 943 ms 35652 KB Output is correct
4 Correct 673 ms 38256 KB Output is correct
5 Correct 266 ms 36172 KB Output is correct
6 Correct 129 ms 35664 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2849 ms 41824 KB Output is correct
2 Correct 2666 ms 41816 KB Output is correct
3 Correct 2746 ms 41660 KB Output is correct
4 Correct 1733 ms 35652 KB Output is correct
5 Correct 1443 ms 38256 KB Output is correct
6 Correct 366 ms 36160 KB Output is correct
7 Correct 149 ms 35660 KB Output is correct