oj.uz

Submission #361269

# Submission time Handle Problem Language Result Execution time Memory
361269 2021-01-29T04:11:04 Z RyoPham Cities (BOI16_cities) C++14
100 / 100
 2248 ms 35988 KB 
#define taskname "test"
 
#include <bits/stdc++.h>
 
using namespace std;
 
#define sz(x) (int)x.size()
#define fi first
#define se second
 
typedef long long lli;
typedef pair<int, int> pii;
typedef pair<lli, int> pli;
 
const int maxn = 1e5 + 5;
const lli inf = 1e17;
 
int n, k, m;
vector<int> specs;
vector<pii> gr[maxn];
 
lli d[(1 << 5) + 5][maxn];
 
template <typename T>
void Read(T& x)
{
    bool Neg = false;
    char c;
    for (c = getchar(); c < '0' || c > '9'; c = getchar())
        if (c == '-') Neg = !Neg;
    x = c - '0';
    for (c = getchar(); c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    if (Neg && x > 0) x = -x;
}
 
void read_input()
{
    //cin >> n >> k >> m;
    Read(n); Read(k); Read(m);
    specs.resize(k);
    for(int i = 0; i < k; ++i)
        Read(specs[i]); //cin >> specs[i];
    for(int i = 1; i <= m; ++i)
    {
        int u, v, w;
        Read(u); Read(v); Read(w);
        //cin >> u >> v >> w;
        gr[u].push_back(pii(v, w));
        gr[v].push_back(pii(u, w));
    }
}
 
priority_queue<pli, vector<pli>, greater<pli>> pq;
 
void dijkstra(int mask)
{
    for(int i = 1; i <= n; ++i)
        if(d[mask][i] != inf) pq.push(pli(d[mask][i], i));
    while(!pq.empty())
    {
        pli cur = pq.top(); pq.pop();
        if(cur.fi != d[mask][cur.se]) continue;
        int u = cur.se;
        for(auto&to: gr[u])
        {
            int v = to.fi, w = to.se;
            if(d[mask][v] > d[mask][u] + w)
            {
                d[mask][v] = d[mask][u] + w;
                pq.push(pli(d[mask][v], v));
            }
        }
    }
}
 
void solve()
{
    for(int i = 0; i < k; ++i)
    {
        int mask = (1 << i);
        fill(d[mask] + 1, d[mask] + n + 1, inf);
        d[mask][specs[i]] = 0;
        dijkstra(mask);
    }
    for(int mask = 1; mask < (1 << k); ++mask)
    {
        if(__builtin_popcount(mask) == 1) continue;
        fill(d[mask] + 1, d[mask] + n + 1, inf);
        for(int sub1 = mask; sub1 > 0; sub1 = (sub1 - 1) & mask)
        {
            if(sub1 == mask) continue;
            int sub2 = mask ^ sub1;
            for(int i = 1; i <= n; ++i)
                d[mask][i] = min(d[mask][i], d[sub1][i] + d[sub2][i]);
        }
        dijkstra(mask);
    }
    lli ans = inf;
    for(int i = 1; i <= n; ++i)
        ans = min(ans, d[(1 << k) - 1][i]);
    cout << ans << '\n';
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    solve();
}

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 17116 KB Output is correct
2 Correct 534 ms 17016 KB Output is correct
3 Correct 354 ms 13284 KB Output is correct
4 Correct 34 ms 7660 KB Output is correct
5 Correct 258 ms 15844 KB Output is correct
6 Correct 30 ms 7788 KB Output is correct
7 Correct 4 ms 2924 KB Output is correct
8 Correct 3 ms 2924 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3052 KB Output is correct
2 Correct 7 ms 3052 KB Output is correct
3 Correct 5 ms 2944 KB Output is correct
4 Correct 5 ms 2924 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1082 ms 23448 KB Output is correct
2 Correct 1104 ms 23532 KB Output is correct
3 Correct 736 ms 19576 KB Output is correct
4 Correct 563 ms 16220 KB Output is correct
5 Correct 123 ms 9452 KB Output is correct
6 Correct 39 ms 9452 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2231 ms 35988 KB Output is correct
2 Correct 2248 ms 35984 KB Output is correct
3 Correct 2216 ms 35856 KB Output is correct
4 Correct 1570 ms 32188 KB Output is correct
5 Correct 1091 ms 22620 KB Output is correct
6 Correct 206 ms 10852 KB Output is correct
7 Correct 56 ms 9580 KB Output is correct