Submission #92015

#	Time	Username	Problem	Language	Result	Execution time	Memory
92015		Vinhspm	Cities (BOI16_cities)	C++14	100 / 100	2835 ms	49880 KiB

cities

#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define FOR(a, b, c) for(int a = b; a <= c; ++a)
#define pb push_back
#define int long long
typedef pair<int, int> ii;
const int N = 1e5 + 10;
const int oo = 1e18;

int n, m, k;
int d[(1 << 6)][N];
vector<ii> vi[N];



signed main()
{
    scanf("%lld%lld%lld", &n, &k, &m);
    FOR(i, 1, n) FOR(j, 0, (1 << k)) d[j][i] = oo;
    FOR(i, 1, k)    {
        int x; scanf("%lld", &x);
        d[(1 << (i - 1))][x] = 0;
    }
    FOR(i, 1, m)    {
        int u, v, c; scanf("%lld%lld%lld", &u, &v, &c);
        vi[u].pb(ii(v, c)); vi[v].pb(ii(u, c));
    }
    FOR(mask, 1, (1 << k) - 1) {
        FOR(j, 1, n) for(int submask = mask; submask; submask = (submask - 1) & mask)
            d[mask][j] = min(d[mask][j], d[mask ^ submask][j] + d[submask][j]);
        priority_queue<ii, vector<ii>, greater<ii> > pq;
        FOR(i, 1, n)  pq.push(ii(d[mask][i], i));
        while(!pq.empty())  {
            int u = pq.top().se, du = pq.top().fi; pq.pop();
            if(du != d[mask][u]) continue;
            for(auto v: vi[u])  if(d[mask][v.fi] > du + v.se)   {
                d[mask][v.fi] = du + v.se;
                pq.push(ii(du + v.se, v.fi));
            }
        }
    }
    int ans = oo;
    FOR(i, 1, n) ans = min(ans, d[(1 << k) - 1][i]);
    printf("%lld", ans);
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld%lld", &n, &k, &m);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:24:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x; scanf("%lld", &x);
                ~~~~~^~~~~~~~~~~~
cities.cpp:28:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v, c; scanf("%lld%lld%lld", &u, &v, &c);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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