Submission #1270735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270735		notisora	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	270 ms	19748 KiB

commuter_pass

///NotIsora
///This is my last dance
#include<bits/stdc++.h>
#define modulo 1000000007
#define fi first
#define se second
#define sq(x) (x)*(x)
#define ll long long
#define ld long double
#define el '\n'
#define pb push_back
///#define int long long

using namespace std;

const int N=1e5+5;
const ll INF=1e15+5;
int n,m;
int S,T,U,V;
vector<pair<int,int>>adj[N];
ll d[4][N];
ll ans=INF;
bool vis[N];
ll dp[N];

void dijkstra(int start,int t){
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>pq;
    d[t][start]=0;
    pq.push({0,start});
    while(!pq.empty()){
        int s=pq.top().se;
        ll dis=pq.top().fi;
        pq.pop();
        if (dis>d[t][s]) continue;
        for(pair<int,int>&pr:adj[s]){
            int u=pr.fi;
            int w=pr.se;
            if (d[t][u]>dis+(ll)w){
                d[t][u]=dis+(ll)w;
                pq.push({d[t][u],u});
            }
        }
    }
}

void dfs(int node,int type){
    vis[node]=1;
    dp[node]=d[2][node];
    for(pair<int,int>&pr:adj[node]){
        int u=pr.fi;
        int w=pr.se;
        if (d[type][node]==d[type][u]+(ll)w){
            if (!vis[u]) dfs(u,type);
            dp[node]=min(dp[node],dp[u]);
        }
    }
    ans=min(ans,dp[node]+d[3][node]);
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("BUS.INP","r",stdin);
    //freopen("BUS.OUT","w",stdout);
    cin>>n>>m;
    cin>>S>>T>>U>>V;
    for(int i=1;i<=m;i++){
        int a,b,w;
        cin>>a>>b>>w;
        adj[a].pb({b,w});
        adj[b].pb({a,w});
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<4;j++){
            d[j][i]=INF;
        }
    }

    dijkstra(S,0);
    dijkstra(T,1);
    dijkstra(U,2);
    dijkstra(V,3);

    ans=d[2][V];

    for(int i=1;i<=n;i++){
        dp[i]=INF;
        vis[i]=0;
    }
    dfs(S,1);
    for(int i=1;i<=n;i++){
        dp[i]=INF;
        vis[i]=0;
    }
    dfs(T,0);

    cout<<ans;
}

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