Submission #854785

#	Time	Username	Problem	Language	Result	Execution time	Memory
854785		hungnt	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	143 ms	19624 KiB

commuter_pass

#include <bits/stdc++.h>
#define pii pair<long long, int>
#define fi first
#define se second
using namespace std;

const int N = 100005;
const long long inf = 1e18;

int n, m;
int S, T, U, V;
vector<pair<int, int>> adj[N];
long long dist[N];
int pre[N];
priority_queue<pii, vector<pii>, greater<pii>> pq;

void dijkstra(int st, int en, long long d[])
{
    for(int i = 1; i <= n; i++) d[i] = inf;
    d[st] = 0;
    pq.push({0, st});
    while(!pq.empty())
    {
        int u = pq.top().se;
        long long w = pq.top().fi;
        pq.pop();
        if(d[u] != w) continue;
        for(auto x : adj[u])
        {
            int v = x.fi, wei = x.se;
            if(d[v] > d[u] + wei)
            {
                d[v] = d[u] + wei;
                pre[v] = u;
                pq.push({d[v], v});
            }
        }
    }
}

void sub1()
{
    dijkstra(S, T, dist);
    int id = T, p;
    while(id != S)
    {
        p = pre[id];
        adj[id].push_back({p, 0});
        adj[p].push_back({id, 0});
        id = p;
    }
    dijkstra(U, V, dist);
    cout << dist[V];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    cin >> S >> T >> U >> V;
    int u, v, w;
    while(m--)
    {
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    sub1();
    return 0;
}

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