Submission #1214848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214848		papaulo	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	492 ms	65048 KiB

commuter_pass

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

typedef long long ll;
#define MAXN 100100

#define RNG(i, n) for(int i=0;i<n;i++)

struct Edge{
    int u, w;
    Edge() : u(0), w(0) {}
    Edge(int u, int w) : u(u), w(w) {}
};

struct Edge2 {
    int u, j, w;
    Edge2() : u(0), j(0), w(0) {}
    Edge2(int u, int j, int w) : u(u), j(j), w(w) {}
};

ll du[MAXN];
ll dv[MAXN];
vector<Edge> adj[MAXN];
bool visited[MAXN];
bool v2[MAXN][4];
ll dist[MAXN];
vector<Edge2> adj2[MAXN][4];
ll d2[MAXN][4];
vector<ll> opt[MAXN];

int n;

void basicDjikstra(int u, ll *d) {
    RNG(i, n) d[i]=LONG_LONG_MAX;
    memset(visited, 0, sizeof(visited));
    d[u]=0;
    priority_queue<pair<ll, int>> pq;
    pq.push({0, u});
    while(!pq.empty()) {
        pair<ll, int> pr=pq.top();
        pq.pop();
        int v=pr.second;
        if(visited[v]) continue;
        visited[v]=true;
        ll curd=d[v];
        for(auto e : adj[v]) {
            int u=e.u;
            int w=e.w;
            ll newd=curd+w;
            if(newd<d[u]) {
                d[u]=newd;
                pq.push({-newd, u});
            }
        }
    }
}

int main() {
    int m, s, t, u, v;
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;
    s--;
    t--;
    u--;
    v--;
    RNG(i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        adj[a].push_back(Edge(b, c));
        adj[b].push_back(Edge(a, c));
    }
    basicDjikstra(u, du);
    RNG(i, n) dist[i]=LONG_LONG_MAX;
    memset(visited, 0, sizeof(visited));
    priority_queue<pair<ll, int>> pq;
    pq.push({0, s});
    dist[s]=0;
    while(!pq.empty()) {
        pair<ll, int> pr=pq.top();
        pq.pop();
        int v=pr.second;
        if(visited[v]) continue;
        visited[v]=true;
        ll curd=dist[v];
        for(auto e : adj[v]) {
            int to=e.u;
            int w=e.w;
            ll newd=curd+w;
            if(newd<dist[to]) {
                dist[to]=newd;
                pq.push({-newd, to});
                opt[to].clear();
            }
            if(newd<=dist[to]) {
                opt[to].push_back(v);
            }
        }
    }
    RNG(i, n) {
        for(auto e : adj[i]) {
            adj2[i][0].push_back(Edge2(e.u, 0, e.w));
            adj2[i][3].push_back(Edge2(e.u, 3, e.w));
        }
        RNG(j, 3) {
            for(int k=j+1;k<4;k++) {
                if(j==1&&k==2) continue;
                adj2[i][j].push_back(Edge2(i, k, 0));
            }
        }
    }
    memset(visited, 0, sizeof(visited));
    stack<int> st;
    st.push(t);
    visited[t]=true;
    while(!st.empty()) {
        int v=st.top();
        st.pop();
        for(auto u : opt[v]) {
            adj2[u][1].push_back(Edge2(v, 1, 0));
            adj2[v][2].push_back(Edge2(u, 2, 0));
            if(visited[u]) continue;
            visited[u]=true;
            st.push(u);
        }
    }
    priority_queue<pair<ll, pair<int, int>>> pq2;
    pq2.push({0, {u, 0}});
    memset(v2, 0, sizeof(v2));
    RNG(i, n) RNG(j, 4) d2[i][j]=LONG_LONG_MAX;
    d2[u][0]=0;
    while(!pq2.empty()) {
        pair<ll, pair<int, int>> pr = pq2.top();
        pq2.pop();
        int v=pr.second.first;
        int j=pr.second.second;
        if(v2[v][j]) continue;
        ll d=d2[v][j];
        v2[v][j]=true;
        for(auto e : adj2[v][j]) {
            ll newd=d+e.w;
            ll &cur=d2[e.u][e.j];
            if(newd<cur) {
                cur=newd;
                pq2.push({-newd, {e.u, e.j}});
            }
        }
    }
    cout << d2[v][3] << endl;
}

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