Submission #41166

#	Time	Username	Problem	Language	Result	Execution time	Memory
41166		ngkan146	Commuter Pass (JOI18_commuter_pass)	C++11	100 / 100	402 ms	97436 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct edge{
    int v, w;
    edge(int v=0,int w=0): v(v), w(w) {}
};
int n,m,s,t,u,v;
vector <edge> G[100005];
vector <int> dag[100005];
ll dis[100005], disS[100005], disU[100005], disV[100005];
bool visited[100005];
priority_queue <pair<long long,int>, vector<pair<long long,int> >, greater<pair<long long, int> > > pq;
void dijkstra(int root){
    fill(dis+1,dis+n+1, (ll) 1e18);
    fill(visited,visited+n+1,0);
    dis[root] = 0;
    pq.push(pair<ll,int>(0ll, root));
    while(pq.size()){
        int u = pq.top().second;
        pq.pop();
        if (visited[u]) continue;
        visited[u] = 1;
        for(auto v: G[u]){
            if (dis[v.v] > dis[u] + v.w)
                dis[v.v] = dis[u] + v.w,
                pq.push(pair<ll,int>(dis[v.v], v.v));
        }
    }
}
void trailBack(int u){
    if (visited[u]) return;
    visited[u] = 1;
    for(auto v: G[u]){
        if (disS[v.v] == disS[u] - v.w)
            dag[v.v].push_back(u),
            trailBack(v.v);
    }
}
ll ans = (ll) 1e18;
ll value[100005];
void dfs(int u){
    value[u] = (ll) disV[u];
    for(int v: dag[u]){
        if (value[v] == -1) dfs(v);
        value[u] = min(value[u], value[v]);
    }
    ans = min(ans, disU[u] + value[u]);
}
int main(){
    iostream::sync_with_stdio(0);
    cin >> n >> m >> s >> t >> u >> v;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        G[a].push_back(edge(b, c));
        G[b].push_back(edge(a, c));
    }
    dijkstra(s);
    for(int i=1;i<=n;i++)   disS[i] = dis[i];
    fill(visited+1,visited+n+1,0);
    trailBack(t);
    dijkstra(u);
    for(int i=1;i<=n;i++)   disU[i] = dis[i];
    ans = disU[v];
    dijkstra(v);
    for(int i=1;i<=n;i++)   disV[i] = dis[i];
    fill(value+1,value+1+n,-1);
    dfs(s);
    swap(disU, disV);
    fill(value+1,value+1+n,-1);
    dfs(s);
    cout << ans;
}

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