제출 #786722

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
786722		12345678	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	228 ms	22332 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5;
ll n, m, s, t, a, b, u, v, w, ans, dp[nx][2];
bool vs[nx];
vector<vector<pair<ll, ll>>> d(nx);
vector<ll> S(nx), A(nx), B(nx);

void dij(int u, vector<ll> &v)
{
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    for (int i=1; i<=n; i++) v[i]=1e16;
    v[u]=0;
    pq.push({0, u});
    while (!pq.empty())
    {
        auto [cw, cl]=pq.top();
        pq.pop();
        for (auto [nl, nw]:d[cl])
        {
            if (v[nl]>cw+nw)
            {
                pq.push({cw+nw, nl});
                v[nl]=cw+nw;
            }
        }
    }
}

void dfs(int u)
{
    if (vs[u]) return;
    vs[u]=1;
    dp[u][0]=A[u];
    dp[u][1]=B[u];
    for (auto [nl, nw]:d[u])
    {
        if (S[nl]+nw==S[u])
        {
            dfs(nl);
            dp[u][0]=min(dp[u][0], dp[nl][0]);
            dp[u][1]=min(dp[u][1], dp[nl][1]);
        }
    }
    ans=min({ans, dp[u][0]+B[u], dp[u][1]+A[u]});
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>s>>t>>a>>b;
    for (int i=0; i<m; i++) cin>>u>>v>>w, d[u].push_back({v, w}), d[v].push_back({u, w});
    dij(s, S);
    dij(a, A);
    dij(b, B);
    for (int i=1; i<=n; i++) dp[i][0]=dp[i][1]=1e16;
    ans=A[b];
    dfs(t);
    cout<<ans;
}

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