제출 #765462

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765462		wmuree	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	276 ms	21556 KiB

commuter_pass

    /*
Muqalzhar taui
*/
#include <bits/stdc++.h>
#include <iomanip>
 
#define ll long long
#define pb push_back
#define F first
#define S second
#define nl '\n'
#define all(x) x.begin(), x.end()
 
const int N = 2e5 + 7;
const int modd = 1e9 + 7;
const int INF = 1e9 + 7;
const double pi = 3.141592653589793238462643383279502884197;
const double EPS = 0.0000000000001;
using namespace std;
  
int gcd(int a, int b){
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
 
ll binpow(ll a, ll x){
    if(x == 0) return 1;
    if(x % 2 == 0){
        ll y = binpow(a, x / 2);
        return (y * y);
    }
    else{
        return (binpow(a, x - 1) * a);
    }
}

ll n, m, s, t, u, v;
vector <pair <ll, ll>> e[N];
ll dpu[N];
ll dpv[N];
ll du[N];
ll dv[N];
void Muqaltin(){  
    cin >> n >> m >> s >> t >> u >> v;
    for(int i = 1; i <= m; i++){
        ll a,b,c;
        cin >> a >> b >> c;
        e[a].pb({b, c});
        e[b].pb({a, c});
    }
    for(int i = 1; i <= n; i++){
        du[i] = INF;
        dv[i] = INF;
        dpu[i] = INF;
        dpv[i] = INF;
    }
    set <pair <ll, ll>> q;
    dv[t] = 0;
    q.insert({dv[t], t});
    while(!q.empty()){
        ll x = q.begin()->second;
        q.erase(q.begin());

        for(auto to : e[x]){
            if(dv[to.F] > dv[x] + to.S){
                q.erase({dv[to.F], to.F});
                dv[to.F] = dv[x] + to.S;
                q.insert({dv[to.F], to.F});
            }
        }
    }
    du[s] = 0;
    q.insert({du[s], s});
    while(!q.empty()){
        ll x = q.begin()->second;
        q.erase(q.begin());

        for(auto to : e[x]){
            if(du[to.F] > du[x] + to.S){
                q.erase({du[to.F], to.F});
                du[to.F] = du[x] + to.S;
                q.insert({du[to.F], to.F});
            }
        }
    }
    
    set <pair <ll, ll>> st;
    dpu[u] = 0;
    st.insert({dpu[u], u});
    while(!st.empty()){
        ll x = st.begin()->second;
        st.erase(st.begin());

        for(auto to : e[x]){
            if(du[x] + to.S + dv[to.F] != du[t]){
                if(dpu[to.F] > dpu[x] + to.S){
                    st.erase({dpu[to.F], to.F});
                    dpu[to.F] = dpu[x] + to.S;
                    st.insert({dpu[to.F], to.F});
                }
            }
            else{
                if(dpu[to.F] > dpu[x]){
                    st.erase({dpu[to.F], to.F});
                    dpu[to.F] = min(dpu[x], du[to.F]);
                    st.insert({dpu[to.F], to.F});
                }
            }
        }
    }
    cout << dpu[v];
    return;
}
 
int main(){
    // freopen("pails.in", "r", stdin);
    //  freopen("pails.out", "w", stdout);
    ios_base :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t = 1;
    // cin >> t;
    while(t--){
        Muqaltin();
    }
    return 0;
}

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