oj.uz

Submission #485807

# Submission time Handle Problem Language Result Execution time Memory
485807 2021-11-09T11:59:02 Z radal Cities (BOI16_cities) C++14
14 / 100
 408 ms 37400 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<ll,int> pll;
typedef pair<long double,long double> pld;
const long long int N = 2e5+10,mod = 998244353,inf = 2e18,maxm = (1 << 24);
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
inline int poww(int n,ll k){
    int c = 1;
    while (k){
        if (k&1) c = (1ll*c*n)%mod;
        n = (1ll*n*n)%mod;
        k >>= 1;
    }
    return c;
}
vector<pll> adj[N];
int n,k,ind[N],par[N][10];
ll d[N][10];
void dij(int v,int i){
    d[v][i] = 0;
    par[v][i] = -1;
    priority_queue<pll> pq;
    pq.push({0,v});
    while (!pq.empty()){
        pll u = pq.top();
        pq.pop();
        if (-u.X != d[u.Y][i]) continue;
        for (pll v : adj[u.Y]){
            if (d[v.X][i] > v.Y+d[u.Y][i]){
                d[v.X][i] = v.Y+d[u.Y][i];
                par[v.X][i] = u.Y;
                pq.push({-d[v.X][i],v.X});
            }
        }
    }
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(d,63,sizeof d);
    int m;
    cin >> n >> k >> m;
    vector<int> ve;
    rep(i,0,k){
        int x;
        cin >> x;
        ve.pb(x);
        ind[x] = i;
    }
    rep(i,0,m){
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    rep(i,0,k) dij(ve[i],i);
    ll ans = inf;
    rep(i,1,n+1){
        ll cost = 0;
        rep(j,0,k) cost += d[i][j];
        ans = min(ans,cost);
    }
    vector<int> ve2;
    rep(i,0,k) ve2.pb(ve[i]); 
    sort(ve.begin(),ve.end());
    int t = 0;
    while (true) {
        ll cost = 0;
        rep(i,1,k) cost += d[ve[i]][ind[ve[i-1]]];
        ans = min(ans,cost);
        if (!next_permutation(ve.begin(),ve.end())) break;
        t++;
    }
    rep(i,0,k) ve[i] = ve2[i];
    rep(i,1,n+1){
        rep(j,0,k){
            ll cost = 0,mi = inf;
            rep(x,0,k){
                if (x == j) continue;
                cost += d[i][x];
                mi = min(mi,d[ve[j]][x]);
            }
            ans = min(ans,cost+mi);
        }
    }
    sort(ve.begin(),ve.end());
    while (true){
        int v = ve[1];
        ll mi1 = inf,mi2 = inf;
        while (v != -1){
            mi1 = min(mi1,d[v][ind[ve[2]]]);
            mi2 = min(mi2,d[v][ind[ve[3]]]);
            v = par[v][ind[ve[0]]];
        }
        ans = min(ans,d[ve[0]][ind[ve[1]]]+mi1+mi2);
        if (!next_permutation(ve.begin(),ve.end())) break;
    }
    cout << ans;
    return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20568 KB Output is correct
2 Correct 8 ms 20556 KB Output is correct
3 Correct 8 ms 20568 KB Output is correct
4 Incorrect 9 ms 20684 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 36808 KB Output is correct
2 Correct 267 ms 37400 KB Output is correct
3 Correct 115 ms 29764 KB Output is correct
4 Correct 60 ms 29748 KB Output is correct
5 Correct 217 ms 36888 KB Output is correct
6 Correct 59 ms 29668 KB Output is correct
7 Correct 9 ms 20812 KB Output is correct
8 Correct 9 ms 20812 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 20852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 326 ms 36820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 408 ms 36876 KB Output isn't correct
2 Halted 0 ms 0 KB -