Submission #125638

#	Time	Username	Problem	Language	Result	Execution time	Memory
125638		lyc	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	1433 ms	65508 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MAXN = 1e5+5;
const int MAXM = 2e5+5;

int N,M,S,T,U,V;
vector<ii> al[4*MAXN];
ll d[4*MAXN];
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
vector<int> p[4*MAXN];
queue<int> q;

ll sssp(int S, int T, bool save) {
    if (save) FOR(i,1,N) p[i].clear();
    memset(d,-1,sizeof d);
    d[S] = 0; pq.emplace(0,S);
    while (!pq.empty()) {
        int u = pq.top().sc; ll w = pq.top().fi; pq.pop();
        for (auto v : al[u]) {
            ll x = w+(ll)v.sc;
            if (d[v.fi] == -1 || x < d[v.fi]) { 
                d[v.fi] = x;
                if (save) p[v.fi].clear(), p[v.fi].push_back(u);
                pq.emplace(x,v.fi);
            } else if (x == d[v.fi]) {
                if (save) p[v.fi].push_back(u);
            }
        }
    }
    //cout << "D " << S << " -> " << T << " = " << d[T] << endl;
    return d[T];
}

void build(int S, int x) {
    memset(d,0,sizeof d);
    q.push(S);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto v : p[u]) {
            al[v+x].emplace_back(u+x,0);
            //cout << "\t\tADD " << v << " to " << u << " x " << x << endl;
            if (!d[v]) {
                d[v] = 1;
                q.push(v);
            }
        }
    }
}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;
    cin >> S >> T;
    cin >> U >> V;
    FOR(i,1,M){
        int A,B,C; cin >> A >> B >> C;
        //cout << "E " << A << " " << B << " :: " << C << " (" << i*2 << ")" << endl;
        //cout << "E " << B << " " << A << " :: " << C << " (" << i*2+1 << ")" << endl;
        al[A].emplace_back(B,C);
        al[B].emplace_back(A,C);

        al[A+3*N].emplace_back(B+3*N,C);
        al[B+3*N].emplace_back(A+3*N,C);
    }
    FOR(A,1,N){
        al[A].emplace_back(A+N,0);
        al[A].emplace_back(A+2*N,0);
        al[A+N].emplace_back(A+3*N,0);
        al[A+2*N].emplace_back(A+3*N,0);
    }

    sssp(S,T,1);
    build(T,N);
    sssp(T,S,1);
    build(S,2*N);

    cout << sssp(U,V+3*N,0) << '\n';
}

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