Submission #1040668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040668		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	199 ms	111860 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define lwb lower_bound
#define upb upper_bound

#define TASKNAME "NAME"

void init()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ///freopen(TASKNAME".INP","r",stdin); freopen(TASKNAME".OUT","w",stdout);
}

const int maxN = 1e6+5;
const ll INF = INT_MAX / 2, MOD = 1e9+7, INFLL = 2e18;
const double epsilon = 1e-3;

struct Edge
{
    ll u,v,w;
    Edge(ll _u = 0, ll _v = 0, ll _w = 0) : u(_u), v(_v), w(_w) {}
};

struct Node
{
    ll u, dist;
    Node(ll _u = 0, ll _dist = 0) : u(_u), dist(_dist) {}

    bool operator < (const Node& other) const
    {
        return dist > other.dist;
    }
};

int n, m, a, b, c, d3;
ll d[maxN][3];
priority_queue<Node> pq;
vector<pll> adj[maxN];
vector<Edge> edges;

void dijkstra(int s, int t)
{
    for(int i = 1; i <= n; i++)
    {
        d[i][t] = INFLL;
    }
    pq.push({s, 0});
    d[s][t] = 0;
    while(!pq.empty())
    {
        int u = pq.top().u;
        ll dist = pq.top().dist;
        pq.pop();
        if(dist > d[u][t]) continue;
        for(pll e : adj[u])
        {
            int v = e.fi;
            ll w = e.se;
            if(d[v][t] > d[u][t] + w)
            {
                d[v][t] = d[u][t] + w;
                pq.push({v, d[v][t]});
            }
        }
    }
}

int vis[maxN], vis2[maxN];
ll res = INFLL, dp[maxN], mnc[maxN], mnd[maxN];
vector<int> topo, dag[maxN], rdag[maxN];

void dfs(int u)
{
    vis[u] = 1;
    for(int v : dag[u])
    {
        if(vis[v] == 0)
            dfs(v);
    }
    topo.pb(u);
    vis[u] = 2;
}

void dfs2(int u)
{
    vis2[u] = 1;
    for(int v : rdag[u])
    {
        if(!vis2[v]) dfs2(v);
    }
}

int main()
{
    init();
    cin >> n >> m >> a >> b >> c >> d3;
    for(int i = 1; i <= m; i++)
    {
        ll u,v,w;
        cin >> u >> v >> w;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
        edges.pb({u, v, w});
    }
    dijkstra(a, 0);
    for(Edge e : edges)
    {
        ll u = e.u, v = e.v, w = e.w;
        if(d[v][0] == d[u][0] + w)
        {
            dag[u].pb(v);
            rdag[v].pb(u);
            //cout << u << " -> " << v << '\n';
        }
        else if(d[u][0] == d[v][0] + w)
        {
            dag[v].pb(u);
            rdag[u].pb(v);
            //cout << v << " -> " << u << '\n';
        }
    }
    dijkstra(c, 1);
    dijkstra(d3, 2);
    dfs(a);
    dfs2(b);
    reverse(all(topo));
    for(int i = 1; i <= n; i++)
    {
        dp[i] = INFLL;
        mnc[i] = INFLL;
        mnd[i] = INFLL;
    }
    dp[a] = d[a][1] + d[a][2];
    mnc[a] = d[a][1];
    mnd[a] = d[a][2];
    for(int u : topo)
    {
        if(vis2[u] == 1)
            res = min(res, dp[u]);
        //cout << u << " " << dp[u] << '\n';
        for(int v : dag[u])
        {
            mnc[v] = min({mnc[v], mnc[u], d[v][1] });
            mnd[v] = min({mnd[v], mnd[u], d[v][2] });
            dp[v] = min(dp[v], min(dp[u], min(mnc[u], d[v][1]) + min(mnd[u], d[v][2]) ) );
        }
    }
    res = min(res, d[d3][1]);
    cout << res;
}

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