oj.uz

Submission #84473

# Submission time Handle Problem Language Result Execution time Memory
84473 2018-11-15T11:17:43 Z Flying_dragon_02 Cities (BOI16_cities) C++14
100 / 100
 3505 ms 31004 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int N = 1e5 + 5;

const long long inf = 1e16;

int n, m, k, a[6];

long long d[6][N], d2[6][6][N];

vector<ii> graph[N];

priority_queue<ii, vector<ii>, greater<ii>> pq;

int mymap[N];

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    cin >> n >> k >> m;
    for(int i = 0; i < k; i++)
        cin >> a[i];
    for(int i = 1; i <= m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        graph[u].pb({v, c});
        graph[v].pb({u, c});
    }
    sort(a, a + k);
    for(int i = 0; i < k; i++) {
        for(int j = 1; j <= n; j++)
            d[i][j] = inf;
        d[i][a[i]] = 0;
    }
    for(int j = 0; j < k; j++)
        mymap[a[j]] = j;
    for(int j = 0; j < k; j++) {
        pq.push({d[j][a[j]], a[j]});
        while(!pq.empty()) {
            ii frt = pq.top();
            pq.pop();
            int c = frt.fi;
            int u = frt.se;
            if(c > d[j][u]) continue;
            for(int i = 0; i < graph[u].size(); i++) {
                int v = graph[u][i].fi, w = graph[u][i].se;
                if(d[j][v] > d[j][u] + w) {
                    d[j][v] = d[j][u] + w;
                    pq.push({d[j][v], v});
                }
            }
        }
    }
    for(int o = 0; o < k; o++) {
        for(int j = 0; j < k; j++) {
            if(o == j) continue;
            for(int i = 1; i <= n; i++) {
                d2[o][j][i] = d[o][i] + d[j][i];
                pq.push({d2[o][j][i], i});
            }
            while(!pq.empty()) {
                ii frt = pq.top();
                pq.pop();
                int c = frt.fi;
                int u = frt.se;
                if(c > d2[o][j][u]) continue;
                for(int i = 0; i < graph[u].size(); i++) {
                    int v = graph[u][i].fi, w = graph[u][i].se;
                    if(d2[o][j][v] > d2[o][j][u] + w) {
                        d2[o][j][v] = d2[o][j][u] + w;
                        pq.push({d2[o][j][v], v});
                    }
                }
            }
        }
    }
    if(k == 2)
        cout << d[0][a[1]];
    else if(k == 3) {
        long long mn = inf;
        for(int i = 1; i <= n; i++) {
            do{
                mn = min(mn, d2[mymap[a[0]]][mymap[a[1]]][i] + d[mymap[a[2]]][i]);
            }while(next_permutation(a, a + k));
        }
        cout << mn;
    }
    else if(k == 4) {
        long long mn = inf;
        for(int i = 1; i <= n; i++) {
            do{
                mn = min(mn, d2[mymap[a[0]]][mymap[a[1]]][i] + d2[mymap[a[2]]][mymap[a[3]]][i]);
            }while(next_permutation(a, a + k));
        }
        cout << mn;
    }
    else {
        long long mn = inf;
        for(int i = 1; i <= n; i++) {
            do{
                mn = min(mn, d2[mymap[a[0]]][mymap[a[1]]][i] + d2[mymap[a[2]]][mymap[a[3]]][i] + d[mymap[a[4]]][i]);
            }while(next_permutation(a, a + k));
        }
        cout << mn;
    }

}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:53:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < graph[u].size(); i++) {
                            ~~^~~~~~~~~~~~~~~~~
cities.cpp:75:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int i = 0; i < graph[u].size(); i++) {
                                ~~^~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2888 KB Output is correct
4 Correct 4 ms 3032 KB Output is correct
5 Correct 4 ms 3032 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1504 ms 17876 KB Output is correct
2 Correct 786 ms 17876 KB Output is correct
3 Correct 1498 ms 17876 KB Output is correct
4 Correct 88 ms 17876 KB Output is correct
5 Correct 865 ms 17876 KB Output is correct
6 Correct 86 ms 17876 KB Output is correct
7 Correct 8 ms 17876 KB Output is correct
8 Correct 7 ms 17876 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 17876 KB Output is correct
2 Correct 11 ms 17876 KB Output is correct
3 Correct 11 ms 17876 KB Output is correct
4 Correct 7 ms 17876 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2344 ms 23508 KB Output is correct
2 Correct 1290 ms 23508 KB Output is correct
3 Correct 2195 ms 23508 KB Output is correct
4 Correct 1122 ms 23508 KB Output is correct
5 Correct 182 ms 23508 KB Output is correct
6 Correct 96 ms 23508 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3403 ms 30472 KB Output is correct
2 Correct 3316 ms 31004 KB Output is correct
3 Correct 1951 ms 31004 KB Output is correct
4 Correct 3505 ms 31004 KB Output is correct
5 Correct 1611 ms 31004 KB Output is correct
6 Correct 257 ms 31004 KB Output is correct
7 Correct 107 ms 31004 KB Output is correct