Submission #1065671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065671		windowwife	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	234 ms	70636 KiB

commuter_pass

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e6 + 2;
ll n, m, a, b, c, d, dist[4][maxn], dp[4][maxn], u, v, w, res;
bool visited[maxn], avail[maxn];
struct Edge
{
    ll u, v, w;
}edge[maxn];
vector<int> adj[maxn], dag[maxn], lst;
struct Item
{
    ll u, dist;
    bool operator < (const Item& other) const
    {
        return dist > other.dist;
    }
};
priority_queue<Item> pq;
bool minimize (ll &a, ll b)
{
    if (a == -1 || a > b)
    {
        a = b;
        return true;
    }
    return false;
}
void topo (int u)
{
    avail[u] = true;
    for (int v : dag[u])
        if (!avail[v]) topo(v);
    lst.push_back(u);
}
void dijkstra (int x, int u)
{
    memset(visited, 0, sizeof(visited));
    for (int i = 1; i <= n; i++) dist[x][i] = -1;
    dist[x][u] = 0;
    pq.push({u, 0});
    while (!pq.empty())
    {
        int u = pq.top().u;
        pq.pop();
        if (visited[u]) continue;
        visited[u] = true;
        for (int i : adj[u])
        {
            int v = edge[i].u ^ edge[i].v ^ u;
            if (minimize(dist[x][v], dist[x][u] + edge[i].w)) pq.push({v, dist[x][v]});
        }
    }
}
int main ()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> a >> b >> c >> d;
    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v >> w;
        edge[i] = {u, v, w};
        adj[u].push_back(i);
        adj[v].push_back(i);
    }
    dijkstra(0, a);
    dijkstra(1, b);
    dijkstra(2, c);
    dijkstra(3, d);
    for (int u = 1; u <= n; u++)
    {
        for (int i : adj[u])
        {
            int v = edge[i].u ^ edge[i].v ^ u;
            if (dist[0][u] + dist[1][v] + edge[i].w == dist[0][b]) dag[u].push_back(v);
        }
    }
    topo(a);
    reverse(lst.begin(), lst.end());
    for (int i = 1; i <= n; i++) dp[2][i] = dp[3][i] = -1;
    for (int u : lst)
    {
        minimize(dp[2][u], dist[2][u]);
        for (int v : dag[u]) minimize(dp[2][v], dp[2][u]);
    }
    for (int u : lst)
    {
        minimize(dp[3][u], dist[3][u]);
        for (int v : dag[u]) minimize(dp[3][v], dp[3][u]);
    }
    res = dist[2][d];
    for (int i = 1; i <= n; i++)
    {
        if (dp[2][i] != -1) res = min(res, dp[2][i] + dist[3][i]);
        if (dp[3][i] != -1) res = min(res, dp[3][i] + dist[2][i]);
    }
    cout << res;
}

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