Submission #1269543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269543		trantrungkein	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	231 ms	38528 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long
#define fi           first
#define si           second
#define For(i,a,b)   for (int i = (a), _b =(b); i <= _b; ++i)
#define all(v)       v.begin(), v.end()
#define Unique(v)    v.erase(unique(all(v)), v.end())
#define MASK(i)      (1LL << (i))
#define bit(i,n)     (((n)>>(i)) & 1)
#define Vii          vector<pair<int,int>>
#define setpr(x)     cout<<setprecision(x)<<fixed
#define Prior        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>>
using namespace std;

const int Mod = 1E9 + 7;
const long long INF  = 4E18;
const int N = 2e5 + 1;
int n,m,S,T,X,Y,ds[N],dt[N],dx[N],dy[N];
vector<pair<int,int>> g[N];

void dij(int st, int dist[], vector<pair<int,int>> g_dij[]) {
    For(i,1,n) dist[i] = INF;
    dist[st] = 0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> Q;
    Q.push({0,st});
    while(!Q.empty()) {
        auto [W,u] = Q.top(); Q.pop();
        if(dist[u] < W) continue;
        for(auto [v,w] : g_dij[u]) {
            if(dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                Q.push({dist[v], v});
            }
        }
    }
}

vector<int> topo,topo2;
int vis_topo[N],vis_topo2[N];
vector<int> adj[N],adj2[N];
void Topo(int u) {
    vis_topo[u] = 1;
    for(int v : adj[u])
        if(!vis_topo[v]) Topo(v);
    topo.push_back(u);
}
void Topo2(int u) {
    vis_topo2[u] = 1;
    for(int v : adj2[u])
        if(!vis_topo2[v]) Topo2(v);
    topo2.push_back(u);
}

struct node{int u,v,w;};
vector<node> edges;
int Miny[N],Minx[N];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin >> n >> m;
    cin >> S >> T >> X >> Y;
    For(i,1,m) {
        int u,v,w;
        cin >> u >> v >> w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
        edges.push_back({u,v,w});
    }

    dij(S,ds,g);
    dij(T,dt,g);
    dij(X,dx,g);
    dij(Y,dy,g);

    for(auto [u,v,w] : edges) {
        if(ds[u] + w + dt[v] == ds[T]) {
            adj[u].push_back(v);
            adj2[v].push_back(u);
        }
        else if(dt[u] + w + ds[v] == ds[T]) {
            adj[v].push_back(u);
            adj2[u].push_back(v);
        }
    }

    Topo(S);
    reverse(all(topo));
    Topo2(T);
    reverse(all(topo2));

    For(i,1,n) Minx[i] = Miny[i] = INF;
    int ans = dx[Y];
    Minx[S] = dx[S];
    Miny[S] = dy[S];
    for(int u : topo) {
        for(int v : adj[u]) {
            ans = min({ans, Minx[u]+dy[v], Miny[u]+dx[v]});
            Minx[v] = min(Minx[v], min(Minx[u], dx[v]));
            Miny[v] = min(Miny[v], min(Miny[u], dy[v]));
        }
    }

    For(i,1,n) Minx[i] = Miny[i] = INF;
    Minx[T] = dx[T];
    Miny[T] = dy[T];
    for(int u : topo2) {
        for(int v : adj2[u]) {
            ans = min({ans, Minx[u]+dy[v], Miny[u]+dx[v]});
            Minx[v] = min(Minx[v], min(Minx[u], dx[v]));
            Miny[v] = min(Miny[v], min(Miny[u], dy[v]));
        }
    }

    cout << ans;
}

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