oj.uz

Submission #92015

# Submission time Handle Problem Language Result Execution time Memory
92015 2019-01-01T03:04:50 Z Vinhspm Cities (BOI16_cities) C++14
100 / 100
 2835 ms 49880 KB 
#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

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.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 762 ms 31052 KB Output is correct
2 Correct 736 ms 30400 KB Output is correct
3 Correct 474 ms 20784 KB Output is correct
4 Correct 96 ms 15288 KB Output is correct
5 Correct 425 ms 27728 KB Output is correct
6 Correct 93 ms 15116 KB Output is correct
7 Correct 7 ms 2936 KB Output is correct
8 Correct 6 ms 2936 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3064 KB Output is correct
2 Correct 9 ms 3064 KB Output is correct
3 Correct 7 ms 2936 KB Output is correct
4 Correct 7 ms 3064 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1366 ms 37180 KB Output is correct
2 Correct 1184 ms 36968 KB Output is correct
3 Correct 816 ms 27132 KB Output is correct
4 Correct 686 ms 27712 KB Output is correct
5 Correct 210 ms 18548 KB Output is correct
6 Correct 109 ms 17512 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2835 ms 49876 KB Output is correct
2 Correct 2600 ms 49880 KB Output is correct
3 Correct 2390 ms 49280 KB Output is correct
4 Correct 1667 ms 39548 KB Output is correct
5 Correct 1287 ms 34116 KB Output is correct
6 Correct 292 ms 19864 KB Output is correct
7 Correct 110 ms 17656 KB Output is correct