Submission #1066691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066691		cpismylifeOwO	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	245 ms	32012 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

const long long inf = 1e18;
const long long mod = 1e9 + 7;
const int MaxN = 2e5 + 5;

struct Edge
{
    int u, v;
    long long w;
};

int n, m, a, b, c, d;
Edge arr[MaxN];
vector<int> graph[MaxN];

void Inp()
{
    cin >> n >> m >> a >> b >> c >> d;
    for (int x = 1; x <= m; x++)
    {
        cin >> arr[x].u >> arr[x].v >> arr[x].w;
        graph[arr[x].u].push_back(x);
        graph[arr[x].v].push_back(x);
    }
}

long long F[4][MaxN];
bool visited[MaxN];
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

void Dijkstra(int id, int s)
{
    for (int x = 1; x <= n; x++)
    {
        F[id][x] = inf;
        visited[x] = false;
    }
    while (!pq.empty())
    {
        pq.pop();
    }
    F[id][s] = 0;
    pq.push(make_pair(0, s));
    while (!pq.empty())
    {
        pair<long long, int> p = pq.top();
        pq.pop();
        if (visited[p.second])
        {
            continue;
        }
        visited[p.second] = true;
        F[id][p.second] = p.first;
        for (int x : graph[p.second])
        {
            int v = arr[x].u ^ arr[x].v ^ p.second;
            long long w  = arr[x].w + p.first;
            if (!visited[v])
            {
                pq.push(make_pair(w, v));
            }
        }
    }
}

vector<int> dag[MaxN];
long long PreMinC[MaxN];
long long PreMinD[MaxN];
bool isInDag[MaxN];

void DFS(int u)
{
    PreMinC[u] = F[2][u];
    PreMinD[u] = F[3][u];
    for (int x : dag[u])
    {
        int v = arr[x].u ^ arr[x].v ^ u;
        if (!visited[v])
        {
            visited[v] = true;
            DFS(v);
        }
        PreMinC[u] = min(PreMinC[u], PreMinC[v]);
        PreMinD[u] = min(PreMinD[u], PreMinD[v]);
    }
}

void Exc()
{
    Dijkstra(0, a);
    Dijkstra(1, b);
    Dijkstra(2, c);
    Dijkstra(3, d);
    long long path = min(F[0][b], F[1][a]);
    for (int x = 1; x <= m; x++)
    {
        if (F[0][arr[x].u] + F[1][arr[x].v] + arr[x].w == path)
        {
            isInDag[arr[x].u] = true;
            isInDag[arr[x].v] = true;
            dag[arr[x].u].push_back(x);
        }
        if (F[0][arr[x].v] + F[1][arr[x].u] + arr[x].w == path)
        {
            isInDag[arr[x].u] = true;
            isInDag[arr[x].v] = true;
            dag[arr[x].v].push_back(x);
        }
    }
    for (int x = 1; x <= n; x++)
    {
        visited[x] = false;
    }
    for (int x = 1; x <= n; x++)
    {
        if (!visited[x] && isInDag[x])
        {
            DFS(x);
        }
    }
    long long res = inf;
    for (int x = 1; x <= n; x++)
    {
        if (isInDag[x])
        {
            res = min(res, min(F[2][x] + PreMinD[x], F[3][x] + PreMinC[x]));
        }
        else
        {
            res = min(res, F[2][x] + F[3][x]);
        }
    }
    cout << res;
}

int main()
{
    //freopen("C.INP", "r", stdin);
    //freopen("C.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}

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