Submission #1065513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065513		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	16 / 100	195 ms	43188 KiB

commuter_pass

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

using ld = long double;
using lli = long long;
using T = pair<int, lli>;

const int maxN = 2e5 + 5;
const lli inf = 1e18;

int n, m, a[4];     ///a0 = A, a1 = B, a2 = C, a3 = D
vector<T> adj[maxN];
vector<int> chil[maxN], par[maxN], topo;
lli d[4][maxN], f[maxN];
bool avail[maxN];

struct cmp
{
    bool operator()(T x, T y)
    {
        return x.second > y.second;
    }
};

void read()
{
    cin >> n >> m;
    for(int i = 0; i < 4; ++i)
        cin >> a[i];
    while(m--){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
}

bool relax(int t, int u, int v, lli w)
{
    if(d[t][v] > d[t][u] + w){
        d[t][v] = d[t][u] + w;
        return true;
    }
    return false;
}

void dijkstra()
{
    priority_queue<T, vector<T>, cmp> pq;   ///first là đỉnh, second = d[đỉnh]
    //dijkstra a 0...3
    for(int i = 0; i < 4; ++i){
        fill(d[i] + 1, d[i] + n + 1, inf);
        d[i][a[i]] = 0;
        pq.push({a[i], 0});
        while(!pq.empty()){
            T t = pq.top();
            pq.pop();
            if(d[i][t.first] != t.second) continue;
            int u = t.first;
            for(T x: adj[u])
                if(relax(i, u, x.first, x.second)) pq.push({x.first, d[i][x.first]});
        }
    }
}

void create()
{
    ///với mỗi đỉnh u thuộc đường đi ngắn nhất từ A -> B, lưu chil[u] = danh sách con của u, par[v] là danh sách cha của v
    int B = a[1];
    for(int u = 1; u <= n; ++u){
        if(d[0][u] + d[1][u] == d[0][B]){
            for(T x: adj[u]){
                int v = x.first;
                if(d[0][v] + d[1][v] == d[0][B] && d[0][v] == d[0][u] + x.second){
                    chil[u].push_back(v);
                    par[v].push_back(u);
                }
            }
        }
    }
}

void dfs(int u)
{
    avail[u] = true;
    for(int v: chil[u])
        if(!avail[v]) dfs(v);
    topo.push_back(u);
}

void solve()
{
    ///ta có một đồ thị DAG
    //sắp xếp topo
    fill(avail + 1, avail + n + 1, false);
    dfs(a[0]);
    reverse(topo.begin(), topo.end());
    //duyệt trên danh sách topo
    lli ans = d[2][a[3]];   ///khoảng cách từ C -> D
    for(int v: topo){
        f[v] = d[2][v]; ///ban đầu, f[v] = khoảng cách từ v đến C
        for(int u: par[v])
            f[v] = min(f[u], f[v]);
        ans = min(ans, f[v] + d[3][v]);
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    freopen("C.INP", "r", stdin);
//    freopen(".OUT", "w", stdout);

    read();
    dijkstra();
    create();
    solve();
}

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