Submission #886751

#	Time	Username	Problem	Language	Result	Execution time	Memory
886751		StefanL2005	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	615 ms	33828 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
ifstream in("file.in");

#define make_arc(N, a, b); N.node = a; N.dist = b;
#define ll long long
const ll inf = 1LL * 1000 * 1000 * 1000 * 1000 * 1000 * 1000;

ll best = 0;

struct arc{
    int node;
    ll dist;
    arc(){
        node = 0; dist = 0;
    }
};

bool rule(arc A, arc B)
{
    if (A.dist == B.dist)
        return A.node < B.node;
    return A.dist < B.dist;
}

void Dijkstra(int start, vector<vector<int>> &Vec, vector<vector<int>> &Cost, vector<ll> &D)
{
    D.assign(Cost.size(), inf);
    D[start] = 0;

    arc A; make_arc(A, start, 0);
    set<arc, bool(*)(arc, arc)> Set(rule);
    Set.insert(A);

    while (!Set.empty())
    {
        auto X = *Set.begin();
        Set.erase(X);

        for (int i = 0; i < Vec[X.node].size(); i++)
        {
            int vecin = Vec[X.node][i];

            if (D[X.node] + Cost[X.node][i] < D[vecin])
            {
                D[vecin] = D[X.node] + Cost[X.node][i];
                
                make_arc(A, vecin, 0);
                auto index = Set.lower_bound(A);

                if (index != Set.end() && index->node == vecin)
                    Set.erase(index);
                
                make_arc(A, vecin, D[vecin]);
                Set.insert(A);
            }
        }
    }
}

struct base{
    ll f, s, sum;

    base() {
        f = s = sum = inf;
    }
};
vector<bool> Been;
void TryRoutes(int node, int end, vector<vector<int>> &Vec, vector<vector<int>> &Cost, vector<vector<ll>> &Dist, vector<base> &Bsum)
{
    Been[node] = true;
    Bsum[node].f = Dist[2][node];
    Bsum[node].s = Dist[3][node];
    Bsum[node].sum = Bsum[node].f + Bsum[node].s;

    ll Min1 = Bsum[node].f, Min2 = Bsum[node].s;
    if (node == end)
        return;

    for (int i = 0; i < Vec[node].size(); i++)
    {
        int vecin = Vec[node][i];

        if (Dist[0][node] + Cost[node][i] + Dist[1][vecin] != Dist[0][end])
            continue;

        if (Been[vecin] == false)
            TryRoutes(vecin, end, Vec, Cost, Dist, Bsum);

        Bsum[node].sum = min(Bsum[node].sum, Bsum[vecin].sum);
  
        Min1 = min(Min1, Bsum[vecin].f);
        Min2 = min(Min2, Bsum[vecin].s);
    }

    Bsum[node].sum = min(Bsum[node].sum, Bsum[node].f + Min2);
    Bsum[node].sum = min(Bsum[node].sum, Bsum[node].s + Min1);

    Bsum[node].f = min(Bsum[node].f, Min1);
    Bsum[node].s = min(Bsum[node].s, Min2);
}

int main()
{
    int n, m, S, T, U, V;
    cin>> n >> m;
    cin>> S >> T;
    cin>> U >> V;
    S--; T--; U--; V--;

    vector<vector<int>> Vec(n), Cost(n);
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin>> a >> b >> c;
        a--; b--;

        Vec[a].push_back(b);
        Vec[b].push_back(a);
        Cost[a].push_back(c);
        Cost[b].push_back(c);
    }

    vector<vector<ll>> Dist(4, vector<ll> (n));

    Dijkstra(S, Vec, Cost, Dist[0]);
    Dijkstra(T, Vec, Cost, Dist[1]);
    Dijkstra(U, Vec, Cost, Dist[2]);
    Dijkstra(V, Vec, Cost, Dist[3]);
    //pentru usurinta S-0 T-1 U-2 V-3
    
    best = Dist[2][V];
    vector<base> Bsum(n);
    Been.assign(n, false);

    TryRoutes(S, T, Vec, Cost, Dist, Bsum);
    
    best = min(best, Bsum[S].sum);
    cout<< best;
    
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void Dijkstra(int, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, std::vector<long long int>&)':
commuter_pass.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int i = 0; i < Vec[X.node].size(); i++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void TryRoutes(int, int, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, std::vector<std::vector<long long int> >&, std::vector<base>&)':
commuter_pass.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for (int i = 0; i < Vec[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~

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