제출 #1009144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1009144		devariaota	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	314 ms	23564 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair < int, int >
#define pii pair < int, pair < int, int >>
#define endl "\n"
#define debug  cout << "AXD" << endl; return 0;
#define pb push_back
#define F first
#define S second

const int MAXN = 1e5 + 5;
int n, m;
int s, t, u, v; 
vector < pi > adj[MAXN];
vector < int > dist ( MAXN, 1e18);
vector < int > from ( MAXN, -1);
map < pi, bool > mp;

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m >> s >> t >> u >> v;

    for ( int i = 1; i <= m; i++){
        int x1, x2, x3; cin >> x1 >> x2 >> x3;
        adj[x1].pb({x2, x3});
        adj[x2].pb({x1, x3});
    }

    // subsoal 2
    priority_queue < pi, vector < pi > , greater < pi > > pq; 
    dist[s] = 0;
    pq.push({0, s});

    while ( !pq.empty()){
        int val = pq.top().F, par = pq.top().S;
        pq.pop();

        if ( val > dist[par] ) continue;
        for ( auto [child, weight] : adj[par] ){
            if ( dist[par] + weight < dist[child]){
                dist[child] = dist[par] + weight;
                from[child] = par;
                pq.push({dist[child], child});
            }
        }
    }

    int temp = t;

    while ( temp != s ){
        mp[{temp, from[temp]}] = 1;
        mp[{from[temp], temp}] = 1;
        temp = from[temp];
    }   

    dist.resize(MAXN, 1e18);

    priority_queue < pi, vector < pi > , greater < pi > > pyqe; 
    dist[u] = 0;
    pq.push({0, u});

    while ( !pq.empty()){
        int val = pq.top().F, par = pq.top().S;
        pq.pop();

        if ( val > dist[par] ) continue;
        for ( auto [child, weight] : adj[par] ){
            if ( mp.count({child, par}) ) weight = 0;
            if ( dist[par] + weight < dist[child]){
                dist[child] = dist[par] + weight;
                from[child] = par;
                pq.push({dist[child], child});
            }
        }
    }

    cout << dist[v] << endl;
    

}

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