Submission #75178

#	Time	Username	Problem	Language	Result	Execution time	Memory
75178		bogdan10bos	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	525 ms	40280 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, int> pli;

int N, M, S, T, U, V;
LL d[100005][3];
vector<int> pth;
vector<pii> edg[100005];
priority_queue< pli, vector<pli>, greater<pli> > pq;

class Dijkstra
{
public:
    int nod;
    vector<LL> d;
    void dijkstra(int _nod)
    {
        d.resize(N + 5);
        nod = _nod;
        for(int i = 1; i <= N; i++) d[i] = 1LL << 60;
        while(!pq.empty())  pq.pop();

        d[nod] = 0;
        pq.push({0LL, nod});
        while(!pq.empty())
        {
            int nod = pq.top().second;
            LL val = pq.top().first;
            pq.pop();

            if(d[nod] != val)   continue;

            for(auto &e: edg[nod])
                if(d[e.first] > val + e.second)
                {
                    d[e.first] = val + e.second;
                    pq.push({val + e.second, e.first});
                }
        }
    }

    LL getd(int x) { return d[x]; }
}dS, dT, dU, dV, djk[305];

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d%d", &N, &M);
    scanf("%d%d", &S, &T);
    scanf("%d%d", &U, &V);
    for(int i = 1; i <= M; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        edg[x].push_back({y, z});
        edg[y].push_back({x, z});
    }

    dS.dijkstra(S);
    dT.dijkstra(T);
    dU.dijkstra(U);
    dV.dijkstra(V);

    LL ans = dU.getd(V);
    LL dST = dS.getd(T);

    for(int i = 1; i <= N; i++)
        d[i][0] = d[i][1] = d[i][2] = 1LL << 60;

    d[S][0] = 0;
    d[S][1] = dU.getd(S);
    d[S][2] = dV.getd(S);
    pq.push({0LL, S});
    while(!pq.empty())
    {
        int nod = pq.top().second;
        LL val = pq.top().first;
        pq.pop();

        if(d[nod][0] != val)    continue;

        d[nod][1] = min(d[nod][1], dU.getd(nod));
        d[nod][2] = min(d[nod][2], dV.getd(nod));

        if(val + dT.getd(nod) == dST)
        {
            ans = min(ans, d[nod][1] + dV.getd(nod));
            ans = min(ans, d[nod][2] + dU.getd(nod));
        }

        for(auto e: edg[nod])
        {
            if(d[e.first][0] > val + e.second)
            {
                d[e.first][0] = val + e.second;
                d[e.first][1] = d[nod][1];
                d[e.first][2] = d[nod][2];
                pq.push({val + e.second, e.first});
            }
            else if(d[e.first][0] == val + e.second)
            {
                d[e.first][1] = min(d[e.first][1], d[nod][1]);
                d[e.first][2] = min(d[e.first][2], d[nod][2]);
            }
        }
    }

    printf("%lld\n", ans);

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &S, &T);
     ~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &U, &V);
     ~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &x, &y, &z);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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