Submission #1037855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037855		vjudge1	Cities (BOI16_cities)	C++17	100 / 100	1302 ms	49960 KiB

cities

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 1e5+7;
ll n, k, m, d[1LL<<5][mxn];
vector<vector<pair<ll,ll>>> g(mxn);
struct node {ll u, dist;};
struct cmp {bool operator() (node a, node b) {return a.dist > b.dist;}};
void dijkstra(ll id)
{
    priority_queue<node,vector<node>,cmp> pq;
    for (ll i = 1; i <= n; i++) pq.push({i,d[id][i]});
    while (!pq.empty())
    {
        node u = pq.top(); pq.pop();
        if (d[id][u.u] < u.dist) continue;
        for (pair<ll,ll> i : g[u.u])
        {
            if (d[id][i.fi] > d[id][u.u]+i.se)
            {
                d[id][i.fi] = d[id][u.u]+i.se;
                pq.push({i.fi,d[id][i.fi]});
            }
        }
    }   
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
    cin >> n >> k >> m;
    for (ll i = 0; i < (1LL<<k); i++) for (ll j = 1; j <= n; j++) d[i][j] = 1e18;
    for (ll i = 0; i < k; i++) 
    {
        ll x; cin >> x;
        d[1LL<<i][x] = 0;
    }
    for (ll i = 1; i <= m; i++)
    {
        ll a, b, w; cin >> a >> b >> w;
        g[a].pb({b,w}); g[b].pb({a,w});
    }
    for (ll i = 0; i < (1LL<<k); i++)
    {
        for (ll j = i; j > 0; j = (j-1)&i)
        {
            for (ll kk = 1; kk <= n; kk++) d[i][kk] = min(d[i][kk],d[i^j][kk]+d[j][kk]);
        }
        dijkstra(i);
    }
    ll opt = 1e18;
    for (ll i = 1; i <= n; i++) opt = min(opt, d[(1LL<<k)-1][i]);
    cout << opt;
}

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