Submission #1065484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065484		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++98	100 / 100	195 ms	30332 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
long long m, n, a, b, c, d, x, y, w;
vector<vector<pair<long long, long long>>> Ad;
priority_queue<pair<long long, long long>> PQ;
priority_queue<pair<long long, pair<long long, long long>>> P_Q;
struct Node{
    long long trusum = 2e15, Cdist = 1e15, Ddist = 1e15, ownC = 1e15, ownD = 1e15, Adist=1e15;
};
Node bois[100005];
void dijkstra1(){
    PQ.push({0, c});
    while(!PQ.empty()){
        pair<long long, long long> P = PQ.top();
        PQ.pop();
        if(bois[P.second].ownC != 1e15) continue;
        bois[P.second].ownC = -P.first;
        bois[P.second].Cdist = -P.first;
        for(pair<long long, long long> Q: Ad[P.second]){
            if(bois[Q.first].ownC == 1e15) PQ.push({P.first - Q.second, Q.first});
        }
    }
}
void dijkstra2(){
    PQ.push({0, d});
    while(!PQ.empty()){
        pair<long long, long long> P = PQ.top();
        PQ.pop();
        if(bois[P.second].ownD != 1e15) continue;
        bois[P.second].ownD = -P.first;
        bois[P.second].Ddist = -P.first;
        for(pair<long long, long long> Q: Ad[P.second]){
            if(bois[Q.first].ownD == 1e15) PQ.push({P.first - Q.second, Q.first});
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> a >> b >> c >> d;
    Ad.resize(n+1);
    while(m--){
        cin >> x >> y >> w;
        Ad[x].push_back({y, w});
        Ad[y].push_back({x, w});
    }
    dijkstra1();
    dijkstra2();
    P_Q.push({0, {a, 0}});
    while((!P_Q.empty()) && -P_Q.top().first <= bois[b].Adist){
        pair<long long, pair<long long, long long>> P = P_Q.top();
        P_Q.pop();
        if(bois[P.second.first].Adist < -P.first) continue;
        if(P.second.second != 0){
            bois[P.second.first].trusum = min(bois[P.second.first].trusum, bois[P.second.second].trusum);
            bois[P.second.first].Cdist = min(bois[P.second.first].Cdist, bois[P.second.second].Cdist);
            bois[P.second.first].Ddist = min(bois[P.second.first].Ddist, bois[P.second.second].Ddist);
        }
        bois[P.second.first].trusum = min(bois[P.second.first].trusum, min(bois[P.second.first].Cdist + bois[P.second.first].ownD, bois[P.second.first].Ddist + bois[P.second.first].ownC));
        if(bois[P.second.first].Adist == 1e15){
            for(pair<int, int> Q: Ad[P.second.first]){
                if(bois[Q.first].Adist == 1e15){
                    P_Q.push({P.first - Q.second, {Q.first, P.second.first}});
                }
            }
        }
        bois[P.second.first].Adist = -P.first;
    }
    cout << min(bois[d].ownC, bois[b].trusum);
}

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