Submission #1281064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281064		stephit	Cities (BOI16_cities)	C++20	14 / 100	880 ms	17936 KiB

cities

/*
  __                      
 (_ _|_  _  ._  |_  o _|_ 
 __) |_ (/_ |_) | | |  |_ 
            |             
*/

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define fi first
#define se second
#define endl '\n'
#define debug cout << "NO ERROR", exit(0)
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
const int mod = 1e9 + 7;
const int base = 311;
const int inf = INT_MAX;
const long long inff = LLONG_MAX;
const int d4x[4] = {-1, 1, 0, 0};
const int d4y[4] = {0, 0, 1, -1};
const char c4[4] = {'U', 'D', 'R', 'L'};
const int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

template<class A, class B> bool maximize(A &x, const B &y) { if (x < y) { x = y; return true; } return false; }
template<class A, class B> bool minimize(A &x, const B &y) { if (x > y) { x = y; return true; } return false; }

/*BIGNUM
typedef __int128 BIG;
istream &operator >> (istream &st,BIG &a){string s;a=0;st>>s;bool g=1;for(int i=0;i<s.size();i++){if(i==0&&s[i]=='-'){g=0;continue;}a=a*10+s[i]-'0';}if(!g){a=-a;}return st;}
ostream &operator << (ostream &st,const BIG &a){BIG t=a;if(t==0){st<<0;return st;}if(t<0){st<<'-';t=-t;}string b;while(t!=0){b.push_back((t%10+'0'));t/=10;}reverse(b.begin(),b.end());st<<b;return st;}
//*/

int n, k, m, a[6];
const int N = 2e5 + 5;
using pa = pair<int, ll>;
vector<pa> adj[N];

namespace k2 {
    ll d[N];
    void solve() {
        fill(d + 1, d + n + 1, 1e17);
        priority_queue<pa, vector<pa>, greater<pa>> pq;

        pq.push({0, a[1]});
        d[a[1]] = 0;

        while (!pq.empty()) {
            auto [w, i] = pq.top(); pq.pop();
            if (w > d[i]) continue;

            for (auto [j, c] : adj[i]) {
                if (d[i] + c >= d[j]) continue;
                d[j] = d[i] + c;
                pq.push({d[j], j});
            }
        }

        cout << d[a[2]];
    }
}

namespace k3 {
    ll d[4][N];

    void dijikstra(int x) {
        for (int i = 1; i <= n; i++) d[x][i] = 1e17;
        priority_queue<pa, vector<pa>, greater<pa>> pq;

        pq.push({0, a[x]});
        d[x][a[x]] = 0;

        while (!pq.empty()) {
            auto [w, i] = pq.top(); pq.pop();
            if (w > d[x][i]) continue;

            for (auto [j, c] : adj[i]) {
                if (d[x][i] + c >= d[x][j]) continue;
                d[x][j] = d[x][i] + c;
                pq.push({d[x][j], j});
            }
        }
    }

    void solve() {
        for (int i = 1; i <= 3; i++) dijikstra(i);
        ll ans = inff;
        for (int i = 1; i <= n; i++) {
            //cout << d[1][i] << ' ' << d[2][i] << ' ' << d[3][i] << endl;
            ans = min(ans, d[1][i] + d[2][i] + d[3][i]);
        }
        cout << ans;
    }
}

void DoTest() {
    cin >> n >> k >> m;
    for (int i = 1; i <= k; i++) cin >> a[i];

    for (int i = 1; i <= m; i++) {
        int u, v, c; cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }

    if (k == 2) k2::solve();
    if (k == 3) k3::solve();
}

#define file(name)                     \
    freopen(name ".inp", "r", stdin);  \
    freopen(name ".out", "w", stdout); \

signed main() {
    #ifdef ONLINE_JUDGE
       //file("") 
    #endif

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int test = 1;
    //cin >> test;
    for (int _ = 1; _ <= test; _++) DoTest();
}

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