Submission #698221

#	Time	Username	Problem	Language	Result	Execution time	Memory
698221		Richem	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	1229 ms	43012 KiB

commuter_pass

#include <iostream>
#include <queue>
#include <vector>
#define int long long

using namespace std;

const int MAX_SOMMET = 1e5+42, INF = 1e16;

struct Arete{
    int dest, cost;
};

struct Pq{
    int sommet, dist, type;

    bool operator<(const Pq &autre) const {
        return dist > autre.dist;
    }
};

int nbSommet, nbArete;
int debOpti, finOpti, debReq, finReq;
vector<Arete> adj[MAX_SOMMET];

void input() {
    cin >> nbSommet >> nbArete;
    cin >> debOpti >> finOpti >> debReq >> finReq;
    debOpti--; finOpti--; debReq--; finReq--;

    for(int arete = 0; arete < nbArete; arete++) {
        int u,v,c;
        cin >> u >> v >> c;

        adj[--u].push_back({--v, c});
        adj[v].push_back({u, c});
    }
}

bool vu[MAX_SOMMET][4] = {0};

int dist[MAX_SOMMET];

bool dansPcc[MAX_SOMMET] = {0};

void calcOrdre(int sommet) {
    if(dansPcc[sommet]) {
        return;
    }
    dansPcc[sommet] = 1;

    for(auto voisin : adj[sommet]) {
        if(dist[sommet] == dist[voisin.dest] + voisin.cost) {
            calcOrdre(voisin.dest);
        }
    }
}

int rep = INF;

void pcc(int deb, int fin) {
    for(int sommet = 0; sommet < MAX_SOMMET; sommet++) {
        for(int type = 0; type < 4; type++) {
            vu[sommet][type] = 0;
        }
    }

    priority_queue<Pq> q;

    q.push({deb, 0, 0});

    if(dansPcc[deb]) {
        q.push({deb, 0, 1});
        q.push({deb, 0, 2});
    }

    while(!q.empty()) {
        Pq cur = q.top();
        q.pop();

        if(vu[cur.sommet][cur.type]) {
            continue;
        }
        vu[cur.sommet][cur.type] = 1;

        if(deb == debOpti) {
            dist[cur.sommet] = cur.dist;
        }

        if(cur.sommet == fin && deb == debReq && fin == finReq) {
            rep = min(rep, cur.dist);
        }

        for(auto voisin : adj[cur.sommet]) {
            if(dansPcc[voisin.dest] == 0) {
                int typeNouv = 0;
                if(cur.type > 0) {
                    typeNouv = 3;
                }

                q.push({voisin.dest, cur.dist + voisin.cost, typeNouv});
            }
            else {
                if(cur.type == 0) {
                    q.push({voisin.dest, cur.dist + voisin.cost, 0});
                    q.push({voisin.dest, cur.dist + voisin.cost, 1});
                    q.push({voisin.dest, cur.dist + voisin.cost, 2});
                }
                if(cur.type == 1 && dist[cur.sommet] < dist[voisin.dest]) {
                    q.push({voisin.dest, cur.dist, 1});
                }
                if(cur.type == 2 && dist[cur.sommet] > dist[voisin.dest]) {
                    q.push({voisin.dest, cur.dist, 2});
                }
                q.push({voisin.dest, cur.dist + voisin.cost, 3});
            }
        }
    }

}

signed main() {
    input();

    pcc(debOpti, finOpti);
    calcOrdre(finOpti);
    pcc(debReq, finReq);

    cout << rep;
}

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