Submission #285373

#	Time	Username	Problem	Language	Result	Execution time	Memory
285373		andrewwangva	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	384 ms	262148 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

typedef long long ll;
vector<pair<ll, int>> edge[100001];
ll distu[100001]; ll distv[100001]; ll dists[100001];
bool visited[100001];
vector<pair<ll, ll>> pathc[100001];
ll MAX = 1000000000000000L; ll MOD = 1000000007L;
void djikstra(int s, ll dist[]){
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pair<ll, int> p; p.first = 0; p.second = s;
    pq.push(p);
    dist[s] = 0;
    while(!pq.empty()){
        pair<ll, int> cur = pq.top(); pq.pop();
        if(!visited[cur.second]){
            visited[cur.second] = true;
            for(pair<ll, int> e : edge[cur.second]){
                ll cost = e.first; int next = e.second;
                ll alt = cost + dist[cur.second];
                if(alt <= dist[next]){
                    dist[next] = alt;
                    e.first = dist[next];
                    pq.push(e);
                }
            }
        }
    }
}

void moddjikstra(int s, ll dist[]){
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pair<ll, int> p; p.first = 0; p.second = s;
    pair<ll, ll> fp; fp.first = distu[s]; fp.second = distv[s];
    pq.push(p);  pathc[s].push_back(fp);
    dist[s] = 0;
    while(!pq.empty()){
        pair<ll, int> cur = pq.top(); pq.pop();
        if(!visited[cur.second]){
            visited[cur.second] = true;
            for(pair<ll, int> e : edge[cur.second]){
                ll cost = e.first; int next = e.second;
                ll alt = cost + dist[cur.second];
                if(alt < dist[next]){
                    pathc[next].clear();
                }
                if(alt <= dist[next]){
                    for(pair<ll, ll> p : pathc[cur.second]){
                        if(distu[next] < p.first){
                            p.first = distu[next];
                        }
                        if(distv[next] < p.second){
                            p.second = distv[next];
                        }
                        pathc[next].push_back(p);
                    }
                    dist[next] = alt;
                    e.first = dist[next];
                    pq.push(e);
                }
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; int m; cin >> n >> m;
    int s; int t; int u; int v; cin>>s>>t>>u>>v;
    for(int i = 0; i < m; i++){
        int a,b,c; cin >> a >> b >> c;
        pair<ll, int> d; d.first = c; d.second = b;
        pair<ll, int> e; e.first = c; e.second = a;
        edge[a].push_back(d); edge[b].push_back(e);
    }
    for(int i = 0; i <= 100000; i++){
        dists[i] = MAX;
        distv[i] = MAX;
        distu[i] = MAX;
        visited[i] = false;
    }
    djikstra(u, distu);
    for(int i = 0; i <= 100000; i++)
        visited[i] = false;
    djikstra(v, distv);
    for(int i = 0; i <= 100000; i++)
        visited[i] = false;
    moddjikstra(1, dists);
    ll ans = distu[v];
    for(pair<ll, ll> p : pathc[t]){
        if(p.first + p.second < ans)
            ans = p.first + p.second;
    }
    cout << ans << endl;
    return 0;
}

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