제출 #59639

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59639		Benq	Cities (BOI16_cities)	C++11	100 / 100	1764 ms	68180 KiB

cities

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int n,k,m;
ll sh[5][MX], bes[5][5][MX];
vi imp;

template<int SZ> struct Dijkstra {
    ll dist[SZ];
    vpi adj[SZ];
    priority_queue<pl,vpl,greater<pl>> q;
    
    void addEdge(int a, int b, int c) {
        adj[a].pb({b,c}), adj[b].pb({a,c});
    }
    
    void clr(int x) {
        FOR(i,1,n+1) dist[i] = INF;
        while (sz(q)) q.pop();
        q.push({dist[x] = 0,x});
    }
    
    void clr(int x, int y) {
        while (sz(q)) q.pop();
        FOR(i,1,n+1) q.push({dist[i] = sh[x][i]+sh[y][i],i});
    }
    
    void gen() {
        while (sz(q)) {
            pl x = q.top(); q.pop();
            if (dist[x.s] < x.f) continue;
            for (pi y: adj[x.s]) if (x.f+y.s < dist[y.f])
                q.push({dist[y.f] = x.f+y.s,y.f});
        }
    }
};

Dijkstra<MX> D;

void genPath(int x) {
    D.clr(imp[x]);
    D.gen();
    FOR(i,1,n+1) sh[x][i] = D.dist[i];
}

void genBes(int x, int y) {
    D.clr(x,y);
    D.gen();
    FOR(i,1,n+1) bes[x][y][i] = D.dist[i];
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k >> m; imp.resize(k);
    F0R(i,k) cin >> imp[i];
    while (sz(imp) < 5) imp.pb(imp.front());
    k = 5;
    
    F0R(i,m) {
        int a,b,c; cin >> a >> b >> c;
        D.addEdge(a,b,c);
    }
    F0R(i,k) genPath(i);
    // cout << sh[1][1];
    F0R(i,k) FOR(j,i+1,k) genBes(i,j);

    ll ans = INF;
    FOR(i,1,n+1) F0R(j,k) {
        int x = (j == 0);
        FOR(z,x+1,k) if (z != j) {
            int X = -1, Z = -1;
            F0R(I,k) if (I != j && I != x && I != z) {
                if (X == -1) X = I;
                else Z = I;
            }
            ans = min(ans,sh[j][i]+bes[x][z][i]+bes[X][Z][i]);
        }
    }
    cout << ans;
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

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