제출 #1272625

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272625		zagaro	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	304 ms	32408 KiB

commuter_pass

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
/**zagaro & lauren <3**/
#define mod 1000000007 //1e9 + 7
#define pi acos(-1)
#define wl while
#define str string
#define ENDL "\n"
#define sal ' '
#define tp_set ll
#define prc(n) cout.precision(n);cout<<fixed;
#define ord_set tree<tp_set, null_type, less<tp_set>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef bool bl;
typedef char car;
using namespace std;
using namespace __gnu_pbds;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, m, s, t, u, v, a, b, c, val, nod, par, sum, x, y;
    cin>>n>>m>>s>>t>>u>>v;
    vector<vector<pair<ll,ll> > > adj(n+1);
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    vector<ll> disu(n+1, -1);
    vector<ll> disv(n+1, -1);
    priority_queue<pair<ll,pair<ll,ll> >, vector<pair<ll,pair<ll,ll> > >, greater<pair<ll,pair<ll,ll> > > > pq;
    pq.push({0,{u, -1}});
    wl(!pq.empty()){
        val = pq.top().first;
        nod = pq.top().second.first;
        par = pq.top().second.second;
        pq.pop();
        if(disu[nod] == -1){
            disu[nod] = val;
            for(int i=0;i<adj[nod].size();i++){
                if(adj[nod][i].first != par)pq.push({val+adj[nod][i].second,{adj[nod][i].first, nod}});
            }
        }
    }
    pq.push({0,{v, -1}});
    wl(!pq.empty()){
        val = pq.top().first;
        nod = pq.top().second.first;
        par = pq.top().second.second;
        pq.pop();
        if(disv[nod] == -1){
            disv[nod] = val;
            for(int i=0;i<adj[nod].size();i++){
                if(adj[nod][i].first != par)pq.push({val+adj[nod][i].second,{adj[nod][i].first, nod}});
            }
        }
    }
    vector<pair<ll,ll> > dis(n+1, {-1, -1});
    priority_queue<tuple<ll,ll,ll,ll,ll,ll>, vector<tuple<ll,ll,ll,ll,ll,ll> >, greater<tuple<ll,ll,ll,ll,ll,ll> > > dij;
    dij.push({0, disu[s]+disv[s], disu[s], disv[s], s, -1});
    wl(!dij.empty()){
        tie(val, sum, a, b, nod, par) = dij.top();
        dij.pop();
        if(dis[nod].first == -1){
            dis[nod] = {val, sum};
            for(int i=0;i<adj[nod].size();i++){
                if(adj[nod][i].first != par){
                    x = min(a, disu[adj[nod][i].first]);
                    y = min(b, disv[adj[nod][i].first]);
                    dij.push({val+adj[nod][i].second, x+y, x, y, adj[nod][i].first, nod});
                }
            }
        }
    }
    cout<<min(disu[v], dis[t].second)<<ENDL;
    return 0;
}

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