oj.uz

Submission #84470

# Submission time Handle Problem Language Result Execution time Memory
84470 2018-11-15T11:14:11 Z Flying_dragon_02 Cities (BOI16_cities) C++14
100 / 100
 5079 ms 41388 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;

map<int, int> mymap;

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, 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, 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:52:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < graph[u].size(); i++) {
                            ~~^~~~~~~~~~~~~~~~~
cities.cpp:73: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 2816 KB Output is correct
3 Correct 4 ms 2896 KB Output is correct
4 Correct 4 ms 3040 KB Output is correct
5 Correct 4 ms 3040 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1573 ms 21012 KB Output is correct
2 Correct 797 ms 21012 KB Output is correct
3 Correct 1514 ms 21012 KB Output is correct
4 Correct 88 ms 21012 KB Output is correct
5 Correct 886 ms 21012 KB Output is correct
6 Correct 87 ms 21012 KB Output is correct
7 Correct 9 ms 21012 KB Output is correct
8 Correct 7 ms 21012 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21012 KB Output is correct
2 Correct 12 ms 21012 KB Output is correct
3 Correct 15 ms 21012 KB Output is correct
4 Correct 8 ms 21012 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2378 ms 27800 KB Output is correct
2 Correct 1311 ms 30728 KB Output is correct
3 Correct 2365 ms 30728 KB Output is correct
4 Correct 1280 ms 30728 KB Output is correct
5 Correct 190 ms 30728 KB Output is correct
6 Correct 96 ms 30728 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3903 ms 41008 KB Output is correct
2 Correct 3746 ms 41388 KB Output is correct
3 Correct 2426 ms 41388 KB Output is correct
4 Correct 5079 ms 41388 KB Output is correct
5 Correct 1904 ms 41388 KB Output is correct
6 Correct 311 ms 41388 KB Output is correct
7 Correct 108 ms 41388 KB Output is correct