Submission #75174

#	Time	Username	Problem	Language	Result	Execution time	Memory
75174		bogdan10bos	Commuter Pass (JOI18_commuter_pass)	C++14	40 / 100	509 ms	14532 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;
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);
    if(S == U)
    {
        for(int i = 1; i <= N; i++)
            if(dS.getd(i) + dT.getd(i) == dST)
                ans = min(ans, dV.getd(i));
        printf("%lld\n", ans);
        exit(0);
    }

    if(N <= 300)
    {
        for(int i = 1; i <= N; i++) djk[i].dijkstra(i);

        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= N; j++)
                if( (dS.getd(i) + djk[i].getd(j) + dT.getd(j) == dST) ||
                    (dS.getd(j) + djk[i].getd(j) + dT.getd(i) == dST) )
                    ans = min(ans, dU.getd(i) + dV.getd(j));
        printf("%lld\n", ans);
        exit(0);
    }

    LL mnu = 1LL << 60, mnv = 1LL << 60;
    for(int i = 1; i <= N; i++)
        if(dS.getd(i) + dT.getd(i) == dST)
        {
            mnu = min(mnu, dU.getd(i));
            mnv = min(mnu, dV.getd(i));
        }
    ans = min(ans, mnu + mnv);
    printf("%lld\n", ans);

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:57: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:58: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:59: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:63: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: 0 / 15
• Subtask 3: 24 / 24
• Subtask 4: 0 / 45