Submission #546725

#	Time	Username	Problem	Language	Result	Execution time	Memory
546725		someone	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	427 ms	27532 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
struct Arc {
    int nex, pds;
};
 
struct Sit {
    int i, t;
    
    bool operator <(const Sit& other) const {
        return t > other.t;
    }
};
 
const int N = 1e5 + 42, INF = 1e18 + 42;

bool vu[N];
vector<Arc> adj[N];
int n, m, s, t, u, v, dist[N][4], distv[N], distu[N];

void Dijkstra(int deb, int id) {
    for(int i = 0; i < n; i++)
        dist[i][id] = INF;
    dist[deb][id] = 0;
    priority_queue<Sit> q;
    q.push({deb, 0});
    while(!q.empty()) {
        int i = q.top().i, t = q.top().t;
        q.pop();
        if(t == dist[i][id]) {
            for(Arc arc : adj[i]) {
                if(dist[arc.nex][id] > t + arc.pds) {
                    dist[arc.nex][id] = t + arc.pds;
                    q.push({arc.nex, dist[arc.nex][id]});
                }
            }
        }
    }
}

void DFS(int i) {
    if(vu[i])
        return;
    vu[i] = true;
    distu[i] = dist[i][2];
    distv[i] = dist[i][3];
    for(Arc arc : adj[i])
        if(dist[i][0] + arc.pds == dist[arc.nex][0] && dist[arc.nex][0] + dist[arc.nex][1] == dist[t][0]) {
            DFS(arc.nex);
            distu[i] = min(distu[i], distu[arc.nex]);
            distv[i] = min(distv[i], distv[arc.nex]);
        }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m >> s >> t >> u >> v;
    s--, t--, u--, v--;
    for(int i = 0; i < m; i++) {
        int a, b, pds;
        cin >> a >> b >> pds;
        a--, b--;
        adj[a].push_back({b, pds});
        adj[b].push_back({a, pds});
    }
    
    Dijkstra(s, 0);
    Dijkstra(t, 1);
    Dijkstra(u, 2);
    Dijkstra(v, 3);
    
    for(int i = 0; i < n; i++)
        distu[i] = distv[i] = INF;
    DFS(s);
    
    int ans = dist[v][2];
    for(int i = 0; i < n; i++)
        ans = min(ans, min(distv[i] + dist[i][2], distu[i] + dist[i][3]));
    cout << ans;
}

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