Submission #1269535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269535		trantrungkein	Commuter Pass (JOI18_commuter_pass)	C++20	16 / 100	212 ms	37200 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> , Vii, greater<Pair> >
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())
    {
        int u,W;
        tie(W,u) = Q.top();Q.pop();
        if(dist[u] < W) continue;
        for(auto [v,w] : g_dij[u]) if(dist[v] > dist[u] + w)
               Q.push({dist[v] = dist[u] + w,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);
    //freopen("kein.inp","r",stdin)
    //freopen("kein.out","w",stdout);
    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));
    For(i,1,n) Minx[i] = Miny[i] =  1e18;
    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[u]});
            Minx[v] = min(Minx[u],dx[v]);
            Miny[v] = min(Miny[u],dy[v]);
        }
    }
    For(i,1,n) Minx[i] = Miny[i] =  1e18;
    Minx[S] = dx[S];
    Miny[S] = dy[S];
    for(int u : topo2)
    {
        for(int v : adj2[u])
        {
            ans = min({ans,Minx[u]+dy[v],Miny[u]+dx[u]});
            Minx[v] = min(Minx[u],dx[v]);
            Miny[v] = min(Miny[u],dy[v]);
        }
    }
    cout << ans;
}

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