제출 #330631

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
330631		plourde27	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	684 ms	31692 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];
ll dpU[100005];
ll dpV[100005];
ll distU[100005];
ll distV[100005];
ll distS[100005];
ll tans;
bool vis[100005];
int n;

void dijkstra(int s, ll fill[]) {
    memset(vis, false, sizeof vis);
    
    priority_queue<pair<int, int>> q;
    q.push({0, s});
    
    while (q.size()) {
        iil inf = q.top();
        q.pop();
        
        ll vt = inf.second;
        ll ds = -inf.first;
        
        if (vis[vt]) continue;
        fill[vt] = ds;
        vis[vt] = true;
        
        for (ii a : adj[vt]) {
            q.push({-ds - a.second, a.first});
        }
    }
    
}

void dijkstra2(int s, int e) {
    rep(i, n) dpU[i] = 100000000000000000;
    rep(i, n) dpV[i] = 100000000000000000;
    memset(vis, false, sizeof vis);
    
    priority_queue<pair<int, pair<int, int>>> q;
    
    q.push({0, {s, -1}});
    
    while (q.size()) {
        pair<int, pair<int, int>> inf = q.top();
        q.pop();
        
        int ds = -inf.first;
        int vt = inf.second.first;
        int ls = inf.second.second;
        
        //cout << vt << " " << ds << endl;
        
        if (!vis[vt]) {
            vis[vt] = true;
            
            dpU[vt] = distU[vt];
            dpV[vt] = distV[vt];
            
            distS[vt] = ds;
            
            if (ls != -1) {
                dpU[vt] = min(dpU[vt], dpU[ls]);
                dpV[vt] = min(dpV[vt], dpV[ls]);
            }
            
            for (ii a : adj[vt]) {
                q.push({-ds - a.second, {a.first, vt}});
            }
        }
        else if (ds == distS[vt]) {
            if (min(dpU[ls], distU[vt]) + min(dpV[ls], distV[vt]) <= dpU[vt] + dpV[vt]) {
                dpU[vt] = min(dpU[ls], distU[vt]);
                dpV[vt] = min(dpV[ls], distV[vt]);
            }
        }
    }
    
    /*rep(i, n) cout << distV[i] << " ";
    cout << endl;
    
    rep(i, n) {
        cout << dpU[i] << " " << dpV[i] << endl;
    }
    cout << endl;*/
    
    tans = min(tans, dpU[e] + dpV[e]);
}

void solve() {
    //gen(10000, 20000);
    
    ll 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});
    }
    
    
    dijkstra(u, distU);
    
    dijkstra(v, distV);
    
    tans = 100000000000000000;
    
    dijkstra2(s, t);
    dijkstra2(t, s);
    
    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: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45