제출 #683687

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
683687		yogesh_sane	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	390 ms	23820 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <climits>
using namespace std;
int n, m, s, t, u, v;

vector<vector<pair<int, int>>> adj;
vector<long long>distU, distV, dpU, dpV;
long long const INF = 1e15;
long long ans = INF;

void dijkstras_ST(int start, int end){
    fill(dpU.begin(), dpU.end(), INF);
    fill(dpV.begin(), dpV.end(), INF);
    vector<bool> visited(n+1, false);
    priority_queue<tuple<long long, int, int>> q;       //dist, node, parent
    vector<long long>dist(n+1,INF);
    q.push({0,start, 0});
    dist[start] = 0;
    while(!q.empty()){
        long long dist_node;
        int node, parent;
        tie(dist_node, node, parent) = q.top();
        dist_node *= -1;
        q.pop();
        if(!visited[node]){
            visited[node] = true;
            dist[node] = dist_node;
            dpU[node] = min(distU[node], dpU[parent]);
            dpV[node] = min(distV[node], dpV[parent]);
            for(auto edge : adj[node])
                q.push({-(dist[node]+edge.second),edge.first,node});
        }else if(dist_node == dist[node]){
            if(min(distU[node], dpU[parent]) + min(distV[node], dpV[parent]) <= dpU[node] + dpV[node]){
                dpU[node] = min(distU[node], dpU[parent]);
                dpV[node] = min(distV[node], dpV[parent]);
            }
        }
    }
    ans = min(ans, dpU[end] + dpV[end]);
}
void dijkstras_UV(int start, vector<long long> &dist){
    vector<bool> visited(n+1);
    priority_queue<pair<long long, int>> q;
    q.push({0,start});
    dist[start] = 0;
    while(!q.empty()){
        int node = q.top().second;
        q.pop();
        if(visited[node])
            continue;
        visited[node] = true;
        for(auto edge : adj[node]){
            int next = edge.first;
            int weight = edge.second;
            if(dist[node] + weight < dist[next]){
                dist[next] = dist[node] + weight;
                q.push({-dist[next],next});
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("in.txt","r",stdin);
    cin >> n >> m >> s >> t >> u >> v;
    adj = vector<vector<pair<int, int>>>(n+1);
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }

    distU = vector<long long>(n+1, INF);
    dijkstras_UV(u, distU);

    //base case, travel without pass
    ans = distU[v];    

    distV = vector<long long> (n+1, INF);
    dijkstras_UV(v, distV);

    dpU = vector<long long>(n+1);
    dpV = vector<long long>(n+1);
    dijkstras_ST(s,t);
    dijkstras_ST(t,s);
    cout << ans << '\n';
    return 0;
}

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