Submission #361269

#	Time	Username	Problem	Language	Result	Execution time	Memory
361269		RyoPham	Cities (BOI16_cities)	C++14	100 / 100	2248 ms	35988 KiB

cities

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