Submission #559807

#	Time	Username	Problem	Language	Result	Execution time	Memory
559807		tamthegod	Cities (BOI16_cities)	C++14	100 / 100	3477 ms	74740 KiB

cities

#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<string>
#include<string.h>
#include<cmath>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<cstdio>
#include<bitset>
#include<chrono>
#include<random>
#include<ext/rope>
/* ordered_set
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
*/
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e17;
int n, m, k;
int d[maxN];
int f[maxN][1 << 6];
struct TPQRec
{
    int vertex, dlab;
    bool operator < (const TPQRec& other) const
    {
        return other.dlab < dlab;
    }
    bool Valid() const
    {
        return d[vertex] == dlab;
    }
};
struct TAdj
{
    int v, w;
};
vector<TAdj> adj[maxN];
vector<int> imp;
void ReadInput()
{
    cin >> n >> k >> m;
    for(int i=1; i<=k; i++)
    {
        int x;
        cin >> x;
        imp.pb(x);
    }
    for(int i=1; i<=m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
}
void Dijkstra()
{
    priority_queue<TPQRec> pq;
    for(int i=1; i<=n; i++)
        if(d[i] < oo) pq.push({i, d[i]});
    while(!pq.empty())
    {
        TPQRec r = pq.top();
        pq.pop();
        if(!r.Valid()) continue;
        int u = r.vertex;
        for(TAdj a : adj[u])
        {
            if(d[a.v] > d[u] + a.w)
            {
                d[a.v] = d[u] + a.w;
                pq.push({a.v, d[a.v]});
            }
        }
    }
}
void Solve()
{
    memset(f, 3, sizeof f);
    for(int i=0; i<k; i++)
        f[imp[i]][1 << i] = 0;
    for(int mask=0; mask<(1<<k); mask++)
    {
        for(int mask1=0; mask1<(1<<k); mask1++)
            for(int mask2=0; mask2<(1<<k); mask2++)
            {
                if((mask1 | mask2) != mask) continue;
                for(int i=1; i<=n; i++)
                    f[i][mask] = min(f[i][mask], f[i][mask1] + f[i][mask2]);
            }
        for(int i=1; i<=n; i++) d[i] = f[i][mask];
        Dijkstra();
        for(int i=1; i<=n; i++) f[i][mask] = d[i];
    }
    int res = oo;
    for(int i=1; i<=n; i++) res = min(res, f[i][(1 << k) - 1]);
    cout << res;
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

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