제출 #753324

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

commuter_pass

#include<bits/stdc++.h>
#define Size(x) ((int)(x).size())
#define MASK(i) (1LL<<(i))
#define bit(mask, i) (((mask) >> (i)) & 1)
#define pii pair<long long,int>
using namespace std;
const long long inf = 1e18 + 7;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;
template<class T1, class T2>
    bool Min(T1 &a, T2 b){
        if(a > b){ a = b; return true;}
        return false;
    }

struct Edge{
    int u,v,w;
};
vector<Edge> edge;
vector<long long> minDistU, minDistV, minDistS, minDistT;
int s, t, u, v, n, m;
vector<pair<int,int>> graph[N];
vector<int> new_graph[N], inew_graph[N];
long long dpU[N], dpV[N], idpU[N], idpV[N];

vector<long long> dijkstra(int s){
    vector<long long> minDist;
    minDist.resize(n+1, inf);
    minDist[s] = 0;

    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({minDist[s], s});

    while(!pq.empty()){
        int u = pq.top().second;
        long long du = pq.top().first;
        pq.pop();
        if(du != minDist[u]) continue;


        for(pair<int, int> child : graph[u]){
            int v = child.first, w = child.second;
            if(Min(minDist[v], minDist[u] + w)){
                pq.push({minDist[v], v});
            }
        }
    }
    return minDist;
}
void dfs(int p){
    dpU[p] = minDistU[p];
    dpV[p] = minDistV[p];
    for(int c : inew_graph[p]){
        dfs(c);
        dpU[p] = min(dpU[p], dpU[c]);
        dpV[p] = min(dpV[p], dpV[c]);
    }
}
void dfs2(int p){
    idpU[p] = minDistU[p];
    idpV[p] = minDistV[p];
    for(int c : new_graph[p]){
        dfs2(c);
        idpU[p] = min(idpU[p], idpU[c]);
        idpV[p] = min(idpV[p], idpV[c]);
    }
}
void solve(){
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;


    for(int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
        edge.push_back({u, v, w});
    }

    minDistS = dijkstra(s);
    minDistT = dijkstra(t);
    minDistU = dijkstra(u);
    minDistV = dijkstra(v);

    for(int i = 0; i < m; i++){
        int u = edge[i].u, v = edge[i].v, w = edge[i].w;
        if(minDistS[u] + minDistT[v] + w == minDistS[t]){
            new_graph[u].push_back(v);
            inew_graph[v].push_back(u);
        }

        if(minDistS[v] + minDistT[u] + w == minDistS[t]){
            new_graph[v].push_back(u);
            inew_graph[u].push_back(v);
        }
    }

    dfs(t);
    dfs2(s);

    long long res = minDistU[v];
    for(int u = 1; u <= n; u++){
        for(int v : new_graph[u]){
            res = min(res, dpU[u] + idpV[v]);
            res = min(res, dpV[u] + idpU[v]);
        }
    }
    cout << res << '\n';
}
int main(){
//    freopen("cbarn2.in", "r", stdin);
//    freopen("cbarn2.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

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