Submission #84472

#	Time	Username	Problem	Language	Result	Execution time	Memory
84472		Flying_dragon_02	Cities (BOI16_cities)	C++14	100 / 100	2121 ms	40412 KiB

cities

#include <bits/stdc++.h>

using namespace std;

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

typedef pair<long long, long long> 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();
            long long 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();
                long long 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 (stderr)

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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26