Submission #1201430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201430		MongHwa	Cities (BOI16_cities)	C++20	14 / 100	323 ms	133384 KiB

cities

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

#define ll long long
#define INF 1e17
#define X first
#define Y second

int key[5];
ll dist[5][100005];
ll dist2[5][5][100005];
int perm[5];
bool status[5];
vector<pair<int, ll>> stage[100005];
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
priority_queue<tuple<ll, int, int, int>, vector<tuple<ll, int, int, int>>, greater<tuple<ll, int, int, int>>> pq2;

void dijkstra(int idx, int st)
{
    dist[idx][st] = 0;
    pq.push({0, st});
    while(!pq.empty())
    {
        ll d; int cur;
        tie(d, cur) = pq.top(); pq.pop();

        if(dist[idx][cur] != d)
            continue;
        
        for(auto& nxt : stage[cur])
            if(dist[idx][nxt.X] > d + nxt.Y)
            {
                dist[idx][nxt.X] = d + nxt.Y;
                pq.push({dist[idx][nxt.X], nxt.X});
            }
    }
}

void dijkstra2(int k, int n)
{
    for(int i = 0; i < k; i++)
        for(int j = 0; j < k; j++)
            for(int x = 1; x <= n; x++)
            {
                dist2[i][j][x] = dist[i][x] + dist[j][x];
                pq2.push({dist[i][x]+dist[j][x], i, j, x});
            }

    while(!pq.empty())
    {
        ll d; int u, v, x;
        tie(d, u, v, x) = pq2.top(); pq2.pop();

        if(dist2[u][v][x] != d)
            continue;
        
        for(auto& nxt : stage[x])
            if(dist2[u][v][nxt.X] > d + nxt.Y)
            {
                dist2[u][v][nxt.X] = d + nxt.Y;
                pq2.push({dist2[u][v][nxt.X], u, v, nxt.X});
            }
    }
}

ll solve(int k, int n)
{
    ll ret = INF;
    if(k == 2)
        for(int i = 1; i <= n; i++)
            ret = min(ret, dist[perm[0]][i] + dist[perm[1]][i]);
    else if(k == 3)
        for(int i = 1; i <= n; i++)
            ret = min(ret, dist2[perm[0]][perm[1]][i] + dist[perm[2]][i]);
    else if(k == 4)
        for(int i = 1; i <= n; i++)
            ret = min(ret, dist2[perm[0]][perm[1]][i] + dist2[perm[2]][perm[3]][i]);
    else
        for(int i = 1; i <= n; i++)
            ret = min(ret, dist2[perm[0]][perm[1]][i] + dist2[perm[2]][perm[3]][i] + dist[perm[4]][i]);

    return ret;
}

void permutate(int p, int k, int n, ll& ans)
{
    if(p == k)
        ans = min(ans, solve(k, n));
    else
    {
        for(int i = 0; i < k; i++)
            if(!status[i])
            {
                status[i] = 1;
                perm[p] = i;
                permutate(p+1, k, n, ans);
                status[i] = 0;
            }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, k, m;
    cin >> n >> k >> m;

    for(int i = 0; i < k; i++)
        cin >> key[i];
    
    while(m--)
    {
        int u, v; ll c;
        cin >> u >> v >> c;

        stage[u].push_back({v, c});
        stage[v].push_back({u, c});
    }

    for(int i = 0; i < k; i++)
    {
        fill(dist[i], dist[i]+n+1, INF);
        dijkstra(i, key[i]);
    }

    dijkstra2(k, n);

    ll ans = INF;
    permutate(0, k, n, ans);
    cout << ans << '\n';
}

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