Submission #1195164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195164		Nonbangkok	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	244 ms	17956 KiB

commuter_pass

#include <bits/stdc++.h>
#define coutf(n, m) cout << fixed << setprecision(n) << m
#define forr(i, a, n) for (int i = a; i < n; i++)
#define forl(i, a, n) for (int i = a; i > n; i--)
#define macos ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endll "\n"
#define sp " "
typedef long long ll;
using namespace std;

struct Non{
    int v;
    ll w;

    bool operator < (const Non &rhs)const{
        if(w!=rhs.w)return w>rhs.w;
        return v>rhs.v;
    }
};

const int N = 1e5 + 10;
int n,m,x,y,st,des,a,b;
int p[N];
ll dis[3][N],c,ans,ans1=1e18,ans2=1e18;
vector<pair<int,ll>> adj[N];
priority_queue<Non> q;

void dijkstra(int z, int s){
    forr(i,1,n+1)dis[s][i] = 1e18;
    q.push({z,dis[s][z]=0LL});
    while(!q.empty()){
        int u = q.top().v;
        q.pop();

        for(auto [v,w]:adj[u]){
            if(dis[s][v]>dis[s][u]+w){
                q.push({v,dis[s][v]=dis[s][u]+w});
                if(!s)p[v] = u;
            }
        }
    }
}

int main(){macos;

    cin >> n >> m >> x >> y >> st >> des;
    forr(i,1,n+1)p[i] = i;
    forr(i,0,m){
        cin >> a >> b >> c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }

    dijkstra(x,0);
    dijkstra(st,1);
    dijkstra(des,2);

    for(int u=y;u!=p[u];u=p[u])ans1 = min(ans1,dis[1][u]),ans2 = min(ans2,dis[2][u]);
    ans1 = min(ans1,dis[1][x]),ans2 = min(ans2,dis[2][x]);

    cout << min(dis[1][des],ans1+ans2);

    return 0;
}

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