제출 #1296792

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1296792		nikaa123	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	283 ms	46588 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
#define eb emplace_back
#define mp make_pair
#define pb push_back
#define pp pop_back
#define endl '\n'
#define ff first
#define ss second
#define stop exit(0)
#define sz(x) (int)x.size()
#define pause system("pause")
#define all(x) (x).begin(), (x).end()
#define deb(x) cout << #x << "-" << x << endl

typedef char chr;
typedef string str;
typedef long long ll;
typedef vector<int> vii;
typedef pair<int, int> pii;
 
const long long INF = LLONG_MAX;
const int inf = INT_MAX;
const int mod = 998244353;
const int MOD = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,1,0,-1};
const double PI = 2 * acos(0.0);
 
const int N = 1e6+5;

int n,m;
int S,T,U,V;
int a[N],b[N],c[N];
vector <vector<pii>> v(N);
int ds[N],dv[N],du[N],dt[N];
int dp1[N],dp2[N],dp3[N];
int id[N];

bool check(int a, int b, int c) {
    return (ds[T] == ds[a]+c+dt[b]);
}

inline void test_case() {
    
    cin >> n >> m;
    cin >> S >> T;
    cin >> U >> V;
    for (int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i] >> c[i];
        v[a[i]].pb({b[i],c[i]});
        v[b[i]].pb({a[i],c[i]});
    }
    for (int i = 1; i <= n; i++) {
        ds[i] = du[i] = dv[i] = dt[i] = INF;
    }
    priority_queue <pii, vector <pii>, greater<pii>> q;
    q.push({0,S});
    ds[S] = 0;
    while (!q.empty()) {
        auto [c,f] = q.top();
        q.pop();
        if (c != ds[f]) continue;
        for (auto [to,c1]:v[f]) {
            if (ds[to] > ds[f]+c1) {
                ds[to] = ds[f]+c1;
                q.push({ds[to],to});
            }
        }
    }
    while (!q.empty()) q.pop();
    q.push({0,U});
    du[U] = 0;
    while (!q.empty()) {
        auto [c,f] = q.top();
        q.pop();
        if (c != du[f]) continue;
        for (auto [to,c1]:v[f]) {
            if (du[to] > du[f]+c1) {
                du[to] = du[f]+c1;
                q.push({du[to],to});
            }
        }
    }
    while (!q.empty()) q.pop();
    q.push({0,V});
    dv[V] = 0;
    while (!q.empty()) {
        auto [c,f] = q.top();
        q.pop();
        if (c != dv[f]) continue;
        for (auto [to,c1]:v[f]) {
            if (dv[to] > dv[f]+c1) {
                dv[to] = dv[f]+c1;
                q.push({dv[to],to});
            }
        }
    }
    while (!q.empty()) q.pop();
    q.push({0,T});
    dt[T] = 0;
    while (!q.empty()) {
        auto [c,f] = q.top();
        q.pop();
        if (c != dt[f]) continue;
        for (auto [to,c1]:v[f]) {
            if (dt[to] > dt[f]+c1) {
                dt[to] = dt[f]+c1;
                q.push({dt[to],to});
            }
        }
    }
    iota(id+1,id+1+n,1);
    sort(id+1,id+1+n,[](int a, int b) {
        return (ds[a]<ds[b]);
    });
    for (int i = 1; i <= n; i++) {
        dp1[i] = dp2[i] = INF;
    }
    for (int i = 1; i <= n; i++) {
        dp1[i] = du[i];
    }
    for (int ii = 1; ii <= n; ii++) {
        int i = id[ii];
        for (auto [to,c]:v[i]) {
            if (ds[to]<ds[i]) continue;
            if (!check(i,to,c)) continue;
            dp2[to] = min(dp2[to],dp2[i]);
            dp2[to] = min(dp2[to],dp1[i]);
        }
    }
    int res1 = INF;
    for (int i = 1; i <= n; i++) {
        if (dp2[i] == INF) continue;
        dp3[i] = dp2[i]+dv[i];
        res1 = min(res1,dp3[i]);
    }
    for (int i = 1; i <= n; i++) {
        dp1[i] = dp2[i] = INF;
    }
    for (int i = 1; i <= n; i++) {
        dp1[i] = dv[i];
    }
    for (int ii = 1; ii <= n; ii++) {
        int i = id[ii];
        for (auto [to,c]:v[i]) {
            if (ds[to]<ds[i]) continue;
            if (!check(i,to,c)) continue;
            dp2[to] = min(dp2[to],dp2[i]);
            dp2[to] = min(dp2[to],dp1[i]);
        }
    }
    int res2 = INF;
    for (int i = 1; i <= n; i++) {
        if (dp2[i] == INF) continue;
        dp3[i] = dp2[i]+du[i];
        res2 = min(res2,dp3[i]);
    }
    int res = min(res1,res2);
    int ans = min(res,du[V]);
    cout << ans << endl;    
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    while (T--) test_case();
    return 0;
}

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