제출 #1214843

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1214843		papaulo	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	208 ms	16284 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 Data {
    ll dist;
    ll mu, mv;
    Data() : dist(0), mu(0), mv(0) {}
    Data(ll dist, ll mu, ll mv) : dist(dist), mu(mu), mv(mv) {}
};

ll du[MAXN];
ll dv[MAXN];
vector<Edge> adj[MAXN];
bool visited[MAXN];
Data dist[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);
    basicDjikstra(v, dv);
    RNG(i, n) dist[i].dist=LONG_LONG_MAX;
    memset(visited, 0, sizeof(visited));
    dist[s].mu=du[s];
    dist[s].mv=dv[s];
    priority_queue<pair<ll, int>> pq;
    pq.push({0, s});
    dist[s].dist=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].dist;
        for(auto e : adj[v]) {
            int to=e.u;
            int w=e.w;
            ll newd=curd+w;
            if(newd<dist[to].dist) {
                dist[to].dist=newd;
                dist[to].mu=min(du[to], dist[v].mu);
                dist[to].mv=min(dv[to], dist[v].mv);
                pq.push({-newd, to});
            } else if(newd==dist[to].dist) {
                if(dist[v].mu+dist[v].mv<dist[to].mu+dist[to].mv) {
                    dist[to].mu=dist[v].mu;
                    dist[to].mv=dist[v].mv;
                }
            }
        }
    }
    ll ans=dv[u];
    ll mu=dist[t].mu;
    ll mv=dist[t].mv;
    //cout << ans << endl;
    //cout << mu << endl;
    //cout << mv << endl;
    ans=min(ans, mu+mv);
    cout << ans << endl;
}

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