Submission #834171

#	Time	Username	Problem	Language	Result	Execution time	Memory
834171		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	2080 ms	14412 KiB

commuter_pass

#include <bits/stdc++.h>
#define task "lyson"
//#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define pii pair <int, int>
#define pli pair <ll, int>
#define fi first
#define se second
using namespace std;
typedef long long ll;
const ll oo = 1e18;
const int nmax = 1e5 + 5;
const int LG = 19;
const ll mod = 1e9 + 7;
void start()
{
//    freopen(task".inp","r",stdin);
//    freopen(task".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, m;
int s, t, u, v, x, y, w, dh[nmax];
vector<pii> adj[nmax];
vector<int> dark[nmax];
ll d[nmax][4], dp[nmax];
pli topo[nmax];
priority_queue<pli, vector<pli>, greater<pli>> pq;
bool isdag[nmax];
void dijkstra(int u, int t)
{
    for(int i = 1; i <= n; i++)
        d[i][t] = oo;
    d[u][t] = 0;
    pq.push({d[u][t], u});
    while(!pq.empty())
    {
        pii temp = pq.top();
        if(temp.fi > d[temp.se][t])
            continue;
        pq.pop();
        for(auto &[to, w] : adj[temp.se])
        {
            if(d[to][t] > d[temp.se][t] + w)
            {
                d[to][t] = d[temp.se][t] + w;
                pq.push({d[to][t], to});
            }
        }
    }
}
int main()
{
    start();
    cin >> n >> m;
    cin >> s >> t >> u >> v;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y >> w;
        adj[x].pb({y, w});
        adj[y].pb({x, w});
    }
    dijkstra(s, 0);
    dijkstra(t, 1);
    dijkstra(u, 2);
    dijkstra(v, 3);
//    cout << d[1][1];
    for(int i = 1; i <= n; i++)
    {
        topo[i] = {d[i][0], i};
        dp[i] = d[i][3]; // từ v -> i
    }
    sort(topo + 1, topo + n + 1);
    isdag[t] = true;
    ll ans = oo;
    //dp[x] cost min để từ 1 nút con của x đi đến v
    //truong hop u tren v duoi
    for(int i = n; i >= 1; i--)
    {
        if(isdag[topo[i].se])
        {
            ans = min(ans, d[topo[i].se][2] + dp[topo[i].se]); // min(u->x) + dp[x]
            for(auto &[past, w] : adj[topo[i].se])
            {
                if(d[past][0] + w == d[topo[i].se][0])
                {
                    isdag[past] = true;
                    dp[past] = min(dp[past], dp[topo[i].se]);
                }
            }
        }
    }
//    cout << ans;
    //truong hop v tren u duoi
    memset(isdag, 0, sizeof(isdag));
    isdag[t] = true;
    for(int i = 1; i <= n; i++)
        dp[i] = d[i][2]; // tu u -> i
    for(int i = n; i >= 1; i--)
    {
        if(isdag[topo[i].se])
        {
            ans = min(ans, d[topo[i].se][3] + dp[topo[i].se]); // min(v->x) + dp[x]
            for(auto &[past, w] : adj[topo[i].se])
            {
                if(d[past][0] + w == d[topo[i].se][0])
                {
                    isdag[past] = true;
                    dp[past] = min(dp[past], dp[topo[i].se]);
                }
            }
        }
    }
    ans = min(ans, d[v][2]); // u -> v
    cout << ans;
}

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