제출 #1310569

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310569		b_malinowski	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	326 ms	23208 KiB

commuter_pass

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

vector<vector<pair<i64, i64>>> con;

void Dijkstra(vector<i64>& dij, i64 pocz, i64 N)
{
     priority_queue<pair<i64, i64>, vector<pair<i64, i64>>, greater<pair<i64, i64>>> Q;
     Q.push({0, pocz});
     vector<bool> bylo(N);
     while (!Q.empty())
     {
         pair<i64, i64> akt = Q.top();
         Q.pop();
         if (bylo[akt.second])
         {
             continue;
         }
         bylo[akt.second] = true;
         dij[akt.second] = akt.first;
         for (int i = 0; i < con[akt.second].size(); i++)
         {
             Q.push({akt.first + con[akt.second][i].second, con[akt.second][i].first});
         }
     }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    i64 N, M, S, T, U, V;
    cin >> N >> M >> S >> T >> U >> V;
    S--;
    T--;
    U--;
    V--;
    con.resize(N);
    for (int i = 0; i < M; i++)
    {
        i64 a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        con[a].push_back({b, c});
        con[b].push_back({a, c});
    }

    vector<i64> dis(N), dit(N), div(N), diu(N);
    Dijkstra(dis, S, N);
    Dijkstra(dit, T, N);
    Dijkstra(div, V, N);
    Dijkstra(diu, U, N);
    i64 wynik = diu[V], minn = dis[T];
    vector<pair<i64, i64>> kopu(N);
    for (int i = 0; i < N; i++)
    {
        kopu[i] = {diu[i], i};
    }
    sort(kopu.begin(), kopu.end());
    vector<bool> bylo(N);
    for (int i = 0; i < N; i++)
    {
        i64 poz = kopu[i].second;
        if (dis[poz] + dit[poz] == minn && !bylo[poz])
        {
            queue<i64> Q;
            Q.push(poz);
            while (!Q.empty())
            {
                int akt = Q.front();
                Q.pop();
                if (bylo[akt])
                {
                    continue;
                }
                bylo[akt] = true;
                wynik = min(wynik, div[akt] + kopu[i].first);
                for (int k = 0; k < con[akt].size(); k++)
                {
                    int next = con[akt][k].first, cost = con[akt][k].second;
                    if (dis[next] == dis[akt] - cost && dit[next] == dit[akt] + cost)
                    {
                        Q.push(next);
                    }
                }
            }
        }
    }
    for (int i = 0; i < N; i++)
    {
        bylo[i] = false;
    }
    for (int i = 0; i < N; i++)
    {
        i64 poz = kopu[i].second;
        if (dis[poz] + dit[poz] == minn && !bylo[poz])
        {
            queue<i64> Q;
            Q.push(poz);
            while (!Q.empty())
            {
                int akt = Q.front();
                Q.pop();
                if (bylo[akt])
                {
                    continue;
                }
                bylo[akt] = true;
                wynik = min(wynik, div[akt] + kopu[i].first);
                for (int k = 0; k < con[akt].size(); k++)
                {
                    int next = con[akt][k].first, cost = con[akt][k].second;
                    if (dis[next] == dis[akt] + cost && dit[next] == dit[akt] - cost)
                    {
                        Q.push(next);
                    }
                }
            }
        }
    }

    cout << wynik << "\n";

    return 0;
}

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