제출 #1167681

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167681		kla	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	2096 ms	52540 KiB

commuter_pass

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")

using namespace std;
vector<pair<int, int>>M[100001];
bool biju [100001];
long long U[100001]={};
long long V[100001]={};
long long bals[100001]={};
priority_queue<tuple<int, long long, long long, long long, long long>, vector<tuple<int, long long, long long, long long, long long>>, greater<tuple<int, long long, long long, long long, long long>>>pq;
long long nxt(){
    long long n;
    cin>>n;
    return n;
}
void DjikstrasimU(int sak){
    U[sak]=0, pq.push(make_tuple(sak, 0, 0, 0, 0));
    while(pq.size()!=0){
        int v=get<0>(pq.top());
        long long att=get<1>(pq.top());
        pq.pop();
        for(auto c: M[v]){
            if(att+c.second<U[c.first]){
                    U[c.first]=att+c.second, pq.push(make_tuple(c.first, U[c.first], 0, 0, 0));
            }
        }
    }
}
void DjikstrasimV(int sak){
    V[sak]=0, pq.push(make_tuple(sak, 0, 0, 0, 0));
    while(pq.size()!=0){
        int v=get<0>(pq.top());
        long long att=get<1>(pq.top());
        pq.pop();
        for(auto c: M[v]){
            if(att+c.second<V[c.first]){
                    V[c.first]=att+c.second, pq.push(make_tuple(c.first, V[c.first], 0, 0, 0));
            }
        }
    }
}
long long Djikstra(int sak, int ender, long long iss){
    bals[sak]=0;
    pq.push(make_tuple(sak, 0, V[sak], U[sak], V[sak]+U[sak]));
    while(get<0>(pq.top())!=ender){
        int v=get<0>(pq.top());
        long long att=get<1>(pq.top()), vak=get<2>(pq.top()), uak=get<3>(pq.top()), koop=get<4>(pq.top());
        pq.pop();
        for(auto c: M[v]){
            if(c.second+att<bals[c.first])bals[c.first]=c.second+att, vak=min(vak, V[c.first]), uak=min(uak, U[c.first]), koop=uak+vak, pq.push(make_tuple(c.first, bals[c.first], vak, uak, koop));
        }
    }
    return min(iss, get<4>(pq.top()));
}
int main()
{
    long long  n, m, s, t, u, v, sk1, sk2, sv;
    cin>>n>>m>>s>>t>>u>>v;
    for(int i=0; i<m; i++){
        sk1=nxt(), sk2=nxt(), sv=nxt();
        M[sk1].push_back({sk2, sv});
        M[sk2].push_back({sk1, sv});
    }
    fill(U, U+n+1, LONG_LONG_MAX);
    fill(V, V+n+1, LONG_LONG_MAX);
    fill(bals, bals+n+1, LONG_LONG_MAX);
    DjikstrasimU(u);
    DjikstrasimV(v);
    cout<<Djikstra(s, t, U[v])<<endl;
    return 0;
}

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