Submission #1152509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152509		koukirocks	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	164 ms	18748 KiB

commuter_pass

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;

void Dijkstra(int n,vvector<pll> &G,vector<ll> &dis,ll s) {
    priority_queue<pll> Q;
    vector<bool> vis(n+1);
    dis[s]=0;
    Q.push({0,s});
    while (!Q.empty()) {
        while (!Q.empty() and vis[Q.top().S]) Q.pop();
        if (Q.empty()) break;
        auto [d,v]=Q.top();
        // cout<<v<<" v\n";
        vis[v]=true;
        for (auto [u,w]:G[v]) {
            if (vis[u]) continue;
            if (dis[v]+w<dis[u]) {
                dis[u]=dis[v]+w;
                Q.push({-dis[u],u});
            }
        }
    }
}

int main() {
    speed;
    ll n,m;
    cin>>n>>m;
    ll s,t,x,y;
    cin>>s>>t>>x>>y;
    vvector<pll> G(n+1);
    for (int i=1;i<=m;i++) {
        ll a,b,c;
        cin>>a>>b>>c;
        G[a].push_back({b,c});
        G[b].push_back({a,c});
    }
    vector<ll> diss(n+1,oo),disx(n+1,oo),disy(n+1,oo);
    Dijkstra(n,G,diss,s);
    Dijkstra(n,G,disx,x);
    Dijkstra(n,G,disy,y);
    // for (int i=1;i<=n;i++) cout<<diss[i]<<" ";
    // cout<<"diss\n";
    // for (int i=1;i<=n;i++) cout<<disx[i]<<" ";
    // cout<<"disx\n";
    // for (int i=1;i<=n;i++) cout<<disy[i]<<" ";
    // cout<<"disy\n";
    vector<int> id(n+1);
    iota(all(id),0);
    diss[0]=-1;
    sort(all(id),[&](int a,int b) {
        return diss[a]<diss[b];
    });
    vector<ll> dpx(n+1,oo),dpy(n+1,oo),dpxy(n+1,oo);
    for (int i=1;i<=n;i++) {
        int v=id[i];
        for (auto [u,w]:G[v]) {
            if (diss[u]+w==diss[v]) {
                dpx[v]=min(dpx[v],dpx[u]);
                dpy[v]=min(dpy[v],dpy[u]);
                dpxy[v]=min(dpxy[v],dpxy[u]);
            }
        }
        dpx[v]=min(dpx[v],disx[v]);
        dpy[v]=min(dpy[v],disy[v]);
        dpxy[v]=min({dpxy[v],dpx[v]+disy[v],dpy[v]+disx[v],disx[v]+disy[v]});
    }
    // for (int i=1;i<=n;i++) cout<<dpx[i]<<" ";
    // cout<<"dpx\n";
    // for (int i=1;i<=n;i++) cout<<dpy[i]<<" ";
    // cout<<"dpy\n";
    // for (int i=1;i<=n;i++) cout<<dpxy[i]<<" ";
    // cout<<"dpxy\n";
    cout<<min(dpxy[t],disx[y])<<"\n";
    return 0;
}   

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