Submission #125603

#	Time	Username	Problem	Language	Result	Execution time	Memory
125603		lyc	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	583 ms	22640 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<iii> al[MAXN];
ll d[MAXN];
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
vector<ii> p[MAXN];
bool f[MAXM*2];
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+(f[v.sc.sc] ? 0 : v.sc.fi);
            if (d[v.fi] == -1 || x < d[v.fi]) { 
                d[v.fi] = x;
                if (save) p[v.fi].clear(), p[v.fi].push_back(ii(u,v.sc.sc));
                pq.emplace(x,v.fi);
            } else if (x == d[v.fi]) {
                if (save) p[v.fi].push_back(ii(u,v.sc.sc));
            }
        }
    }
    //cout << "D " << S << " -> " << T << " = " << d[T] << endl;
    return d[T];
}

void mark(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]) {
            f[v.sc] = x;
            if (x == 2) cout << v.fi << " -> " << u << endl;
            if (!d[v.fi]) {
                d[v.fi] = 1;
                q.push(v.fi);
            }
        }
    }
}

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,0,M-1){
        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].push_back(iii(B, ii(C,i*2)));
        al[B].push_back(iii(A, ii(C,i*2+1)));
    }

    sssp(S,T,1);
    mark(T,1);
    ll ans = sssp(U,V,0);
    mark(T,0);
    sssp(T,S,1);
    mark(S,1);
    ans = min(ans, sssp(U,V,0));
    cout << ans << '\n';
    //mark(V,2);
}

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