Submission #426406

#	Time	Username	Problem	Language	Result	Execution time	Memory
426406		Odavey	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	720 ms	29484 KiB

commuter_pass

//
// ~oisín~ C++ Template
//

#include                <bits/stdc++.h>
#define MX_N            200005
#define mp              make_pair
#define mod7            1000000007
#define modpi           314159
#define PI              3.141592653589793238
#define pb              push_back
#define FastIO          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a)          a.begin(),a.end()
#define fi              first
#define se              second
#define ll              long long int
#define ull             unsigned long long int

int kx[8]  =            {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8]  =            {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] =            {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] =            {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] =            {+0, +0, +1, -1};
int dy4[4] =            {+1, -1, +0, +0};

ll gcd(ull a, ull b){
    return (a==0)?b:gcd(b%a,a);
}

ll lcm(ull a, ull b){
    return a*(b/gcd(a,b));
}

const long long INF = 1e18;

using namespace std;

int N, M, S, T, U, V;

bool vis[MX_N];
bool topovis[MX_N];
vector<int> toposort;
ll dist[MX_N][3];
ll mass[MX_N];
vector<pair<int, int> > adj[MX_N];
vector<int> dag_adj[MX_N];

ll dpU[MX_N], dpV[MX_N];

void topodfs(int at){
    topovis[at] = true;
    for(int to : dag_adj[at]){
        if(!topovis[to]){
            topodfs(to);
        }
    }
    toposort.pb(at);
    return;
}

int main(){
    cin >> N >> M >> S >> T >> U >> V;
    --S, --T, --U, --V;
    for(int i=0;i<M;++i){
        int u, v;
        cin >> u >> v >> mass[i];
        --u, --v;
        adj[u].pb({v, i});
        adj[v].pb({u, i});
    }
    for(int i=0;i<N;++i){
        dist[i][0] = dist[i][1] = dist[i][2] = INF;
    }

    priority_queue<pair<ll, int> > pq;
    dist[S][0] = 0ll;
    pq.push({0, S});
    while(!pq.empty()){
        auto [d, at] = pq.top();
        pq.pop();
        d *= -1ll;
        if(d != dist[at][0]){
            continue;
        }
        for(auto& [to, id] : adj[at]){
            if(dist[to][0] > dist[at][0] + mass[id]){
                dist[to][0] = dist[at][0] + mass[id];
                pq.push({-1ll*dist[to][0], to});
            }
        }
    }

    dist[U][1] = 0ll;
    pq.push({0, U});
    while(!pq.empty()){
        auto [d, at] = pq.top();
        pq.pop();
        d *= -1ll;
        if(d != dist[at][1]){
            continue;
        }
        for(auto& [to, id] : adj[at]){
            if(dist[to][1] > dist[at][1] + mass[id]){
                dist[to][1] = dist[at][1] + mass[id];
                pq.push({-1ll*dist[to][1], to});
            }
        }
    }

    dist[V][2] = 0ll;
    pq.push({0, V});
    while(!pq.empty()){
        auto [d, at] = pq.top();
        pq.pop();
        d *= -1ll;
        if(d != dist[at][2]){
            continue;
        }
        for(auto& [to, id] : adj[at]){
            if(dist[to][2] > dist[at][2] + mass[id]){
                dist[to][2] = dist[at][2] + mass[id];
                pq.push({-1ll*dist[to][2], to});
            }
        }
    }

    memset(vis, 0, sizeof(vis));
    queue<int> Q;
    vis[T] = true;
    Q.push(T);
    while(!Q.empty()){
        int at = Q.front();
        Q.pop();
        for(auto& [to, id] : adj[at]){
            if(dist[to][0] + mass[id] == dist[at][0]){
                dag_adj[to].pb(at);
                if(!vis[to]){
                    vis[to] = true;
                    Q.push(to);
                }
            }
        }
    }

    memset(topovis, 0, sizeof(topovis));
    topodfs(S);
    reverse(All(toposort));
    ll ans = dist[V][1];
    for(int i=0;i<N;++i){
        dpU[i] = dist[i][1];
        dpV[i] = dist[i][2];
    }
    for(int at : toposort){
        for(int to : dag_adj[at]){
            dpU[to] = min(dpU[to], dpU[at]);
            dpV[to] = min(dpV[to], dpV[at]);
        }
        ans = min(ans, dpU[at] + dist[at][2]);
        ans = min(ans, dpV[at] + dist[at][1]);
    }
    cout << ans << endl;
}

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