Submission #713004

#	Time	Username	Problem	Language	Result	Execution time	Memory
713004		thimote75	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	534 ms	38276 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

#define num long long
#define t_road pair<int, num>
#define s second
#define cost s
#define f first
#define next f
#define t_roads vector<t_road>
#define graph vector<t_roads>
#define ndata vector<num>
#define dn pair<num, int>

graph roads;
graph residual;
graph residual_r;

vector<dn> propagation;

void dij (int start, vector<num> &res) {
    fill(res.begin(), res.end(), 1e18);
    
    res[start] = 0;

    set<t_road> queue;
    queue.insert({ 0, start });

    while (queue.size() != 0) {
        t_road r = *queue.begin();
        queue.erase(r);

        int curr = r.s;
        int val  = r.f;
        if (val != res[curr]) continue ;

        for (t_road road : roads[curr]) {
            if (res[road.next] <= res[curr] + road.cost) continue ;

            t_road old = { res[road.next], road.next };
            res[road.next] = res[curr] + road.cost;

            if (queue.find(old) != queue.end())
                queue.erase(old);
            queue.insert({ res[road.next], road.next });
        }
    }
}

vector<bool> visited;
void dfs (vector<num> &res, int node) {
    if (visited[node]) return ;
    visited[node] = true;
    propagation.push_back({ res[node], node });

    for (t_road road : roads[node]) {
        if (res[road.next] + road.cost != res[node]) continue ;
    
        residual[node].push_back(road);
        residual_r[road.next].push_back({ node, road.cost });
        
        dfs(res, road.next);
    }
}

void propagate (vector<num> &res, graph &r, int node) {
    for (t_road road : r[node])
        res[road.next] = min(res[road.next], res[node]);
}
void propagate (vector<num> &res, graph &r) {
    for (dn prop_node : propagation)
        propagate(res, r, prop_node.second);
}

void show (vector<num> &res, string s) {
    cout << "--- " << s << " ---" << endl;
    for (int i = 0; i < res.size(); i ++)
        printf("%lld ", res[i]);
    cout << endl;
}

int main () {
    int nbNodes, nbRoads;
    cin >> nbNodes >> nbRoads;

    int h, t, a, b;
    cin >> h >> t >> a >> b;
    h --; t --; a --; b --;

    roads.resize(nbNodes);
    residual.resize(nbNodes);
    residual_r.resize(nbNodes);
    visited.resize(nbNodes, false);

    for (int iR = 0; iR < nbRoads; iR ++) {
        int l, r, cst;
        cin >> l >> r >> cst;
        l --; r --;

        roads[l].push_back({ r, cst });
        roads[r].push_back({ l, cst });
    }

    ndata H(nbNodes), A(nbNodes), B(nbNodes), C(nbNodes);
    dij(h, H);
    dij(a, A);
    dij(b, B);

    dfs (H, t);
    //for (dn data : propagation)
    //    printf("%d ", data.second);
    //cout << endl;

    //show(A, "A0");
    //show(B, "B0");

    for (int id = 0; id < C.size(); id ++) C[id] = A[id];

    sort(propagation.rbegin(), propagation.rend());
    propagate(A, residual);
    reverse(propagation.begin(), propagation.end());
    propagate(C, residual_r);

    //show(H, "H");
    //show(A, "A1");
    //show(B, "B1");

    num answer = 1e18;
    for (int id = 0; id < nbNodes; id ++)
        answer = min(answer, min(C[id], A[id]) + B[id]);

    cout << answer << endl;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void show(std::vector<long long int>&, std::string)':
commuter_pass.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i = 0; i < res.size(); i ++)
      |                     ~~^~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:119:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for (int id = 0; id < C.size(); id ++) C[id] = A[id];
      |                      ~~~^~~~~~~~~~

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