Submission #91015

#	Time	Username	Problem	Language	Result	Execution time	Memory
91015		EntityIT	Cities (BOI16_cities)	C++14	100 / 100	2784 ms	104820 KiB

cities

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define fi first
#define se second
typedef pair<int, int> ii;
typedef pair<long long, int> lli;

const int N = 1e5 + 5;
const long long inf = (long long)1e18 + 123;
int n, K, m;
long long d[1 << 5][N];
vector<int> important;
vector<ii> gr[N];

int main () {
//    freopen("test.INP", "r", stdin);
    for (int mask = 0; mask < (1 << 5); ++mask) {
        for (int i = 0; i < N; ++i) d[mask][i] = inf;
    }

    scanf("%d %d %d", &n, &K, &m);
    important.assign(K, 0);
    for (int i = 0; i < K; ++i) {
        int u; scanf("%d", &u);
        important[i] = u;
        d[1 << i][u] = 0;
    }

    while (m --) {
        int u, v, w; scanf("%d %d %d", &u, &v, &w);
        gr[u].pb(ii(v, w) );
        gr[v].pb(ii(u, w) );
    }

    for (int mask = 1; mask < (1 << K); ++mask) {
        for (int subMask = mask; subMask; subMask = (subMask - 1) & mask) {
            for (int u = 1; u <= n; ++u) d[mask][u] = min(d[mask][u], d[subMask][u] + d[mask ^ subMask][u]);
        }
        priority_queue<lli, vector<lli>, greater<lli> > pq;
        for (int u = 1; u <= n; ++u) pq.push(lli(d[mask][u], u) );
        while (!pq.empty() ) {
            lli tmp = pq.top(); pq.pop();
            int u = tmp.se;
            if (tmp.fi > d[mask][u]) continue ;
            for (ii _ : gr[u]) {
                int v = _.fi, w = _.se;
                if (d[mask][v] > d[mask][u] + w) {
                    d[mask][v] = d[mask][u] + w;
                    pq.push(lli(d[mask][v], v) );
                }
            }
        }
    }

    long long ans = inf;
    for (int u = 1; u <= n; ++u) ans = min(ans, d[(1 << K) - 1][u]);
    printf("%lld", ans);

    return 0;
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:24:10: 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:27:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u; scanf("%d", &u);
                ~~~~~^~~~~~~~~~
cities.cpp:33:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v, w; scanf("%d %d %d", &u, &v, &w);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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