Submission #330621

#	Time	Username	Problem	Language	Result	Execution time	Memory
330621		plourde27	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	1802 ms	262148 KiB

commuter_pass

#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <map>
#include <fstream>
#include <bitset>
#include <unordered_map>
#include <stack>
#include <list>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef map<int, int> mii;
typedef map<int, string> mis;
typedef map<string, int> msi;
typedef set<int> si;
typedef set<ll> sl;
typedef map<ll, ll> mll;
typedef queue<int> qi;
typedef queue<ii> qii;
typedef vector<string> vs;
typedef pair<ll, ll> iil;
typedef priority_queue<int> pqi;
typedef priority_queue<ii> pqii;
typedef priority_queue<ll> pqil;
typedef priority_queue<iil> pqiil;
typedef vector<iil> viil;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int, ii> iii;
typedef pair<iil, ll> iiil;
typedef vector<pair<pair<int,int>,int> > viii;
typedef vector<pair<pair<ll,ll>,ll> > viiil;
typedef vector<vl> vvl;

#define pb push_back
#define mp make_pair
#define rep(i, n) for (int i = 0 ; i < n ; i++)
#define rrep(i, m, n) for (int i = m ; i < n ; i++)
#define per(i, n) for (int i = n - 1 ; i >= 0 ; i--)
#define perr(i, m, n) for (int i = n - 1 ; i >= m ; i--)
#define INF 2000000000
#define int long long

ll MOD = 1000000007;

viil adj[100005];

vl ans[100005];
ll dpU[100005];
ll dpV[100005];
ll distU[100005];
ll distV[100005];
ll distS[100005];
ll vis[100005];
ll tans;

void dfs(int n) {
    if (vis[n]) return;
    vis[n] = true;
    tans = min(tans, dpU[n] + distV[n]);
    tans = min(tans, dpV[n] + distU[n]);
    //cout << n << " " << dpU[n] << " " << dpV[n] << " " << distV[n] << " " << distU[n] << endl;
    for (int a : ans[n]) {
        dfs(a);
    }
}

void solve() {
    ll n, m;
    cin >> n >> m;
    
    ll s, t;
    cin >> s >> t;
    
    s--; t--;
    
    ll u, v;
    cin >> u >> v;
    
    u--; v--;
    
    rep(i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        
        a--; b--;
        adj[a].pb({b, c});
        adj[b].pb({a, c});
    }
    
    pqiil q;
    q.push({0, u});
    
    
    rep(i, n) distU[i] = 100000000000000000;
    
    while (q.size()) {
        iil inf = q.top();
        q.pop();
        
        ll ds = -inf.first;
        ll vt = inf.second;
        
        if (ds > distU[vt]) continue;
        
        distU[vt] = ds;
        
        
        for (iil a : adj[vt]) {
            q.push({-(ds + a.second), a.first});
        }
        
    }
    
    pqiil q2;
    q2.push({0, v});
    
    
    rep(i, n) distV[i] = 100000000000000000;
    
    while (q2.size()) {
        iil inf = q2.top();
        q2.pop();
        
        ll ds = -inf.first;
        ll vt = inf.second;
        
        if (ds > distV[vt]) continue;
        
        distV[vt] = ds;
        
        
        for (iil a : adj[vt]) {
            q2.push({-(ds + a.second), a.first});
        }
        
    }
    
    priority_queue<pair<int, pair<int, int>>> q3;
    q3.push({0, {s, -1}});
    
    
    rep(i, n) distS[i] = 100000000000000000;
    
    rep(i, n) dpU[i] = 100000000000000000;
    
    rep(i, n) dpV[i] = 100000000000000000;
    
    while (q3.size()) {
        pair<int, pair<int, int>> inf = q3.top();
        q3.pop();
        
        ll ds = -inf.first;
        ll vt = inf.second.first;
        ll ls = inf.second.second;
        
        if (ds > distS[vt]) continue;
        distS[vt] = ds;
        
        if (ls != -1) {
            //cout << vt << " " << ls << endl;
            ans[vt].pb(ls);
        }
        
        if (ls != -1) {
            dpU[vt] = min(dpU[vt], dpU[ls]);
            dpV[vt] = min(dpV[vt], dpV[ls]);
        }
        
        dpU[vt] = min(dpU[vt], distU[vt]);
        dpV[vt] = min(dpV[vt], distV[vt]);
        
        //cout << vt << " " << dpV[vt] << endl;
        
        for (iil a : adj[vt]) {
            q3.push({-(ds + a.second), {a.first, vt}});
        }
    }
    
    tans = 100000000000000000;
    
    dfs(t);
    
    tans = min(tans, distU[v]);
    
    cout << tans << endl;
    
    
    
    
}

void querySolve() {
    int t;
    cin >> t;
    for (int i = 0 ; i < t ; i++) {
        solve();
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    solve();
    //querySolve();
}

• Subtask 1: 0 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45