Submission #485379

#	Time	Username	Problem	Language	Result	Execution time	Memory
485379		Richem	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	2068 ms	262148 KiB

commuter_pass

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

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

using namespace std;

struct Arete{
    int dest, cost;

    bool operator<(const Arete &autre) const {
        return cost > autre.cost;
    }
};

int nbSommet, nbArete;
int departPcc, arrivePcc, depart, arrive;

vector<Arete> adj[MAX_SOMMET];

void input() {
    cin >> nbSommet >> nbArete >> departPcc >> arrivePcc >> depart >> arrive;
    departPcc--; arrivePcc--; depart--; arrive--;

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

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

int dist[MAX_SOMMET];
bool vuPcc[MAX_SOMMET] = {0};

bool sommetPcc[MAX_SOMMET] = {0};

void calcPcc() {
    priority_queue<Arete> q;
    q.push({departPcc, 0});

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

        if(vuPcc[cur.dest])
            continue;

        vuPcc[cur.dest] = 1;
        dist[cur.dest] = cur.cost;

        for(auto voisin : adj[cur.dest]) {
            q.push({voisin.dest, cur.cost + voisin.cost});
        }
    }

    queue<int> marque;
    marque.push(arrivePcc);

    while(!marque.empty()) {
        int cur = marque.front();
        marque.pop();

        sommetPcc[cur] = 1;

        for(auto voisin : adj[cur]) {
            if(dist[cur] - dist[voisin.dest] == voisin.cost) {
                marque.push(voisin.dest);
            }
        }
    }
}

struct Situation{
    int sommet, dist, prisPass;
    bool croissant;

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

int reponse[MAX_SOMMET][3][2];
bool vu[MAX_SOMMET][3][2];

bool correct(int a, int b, int c) {
    return (a < b && c) || (b < a && !c);
}

void calcRep() {
    for(int i = 0; i < MAX_SOMMET; i++) {
        for(int j = 0; j < 3; j++) {
            reponse[i][j][0] = reponse[i][j][1] = INF;
        }
    }
    priority_queue<Situation> q;

    q.push({depart, 0, sommetPcc[depart], 0});
    q.push({depart, 0, sommetPcc[depart], 1});

    while(!q.empty()) {
        int cur = q.top().sommet, pass = q.top().prisPass, curDist = q.top().dist, crois = q.top().croissant;
        q.pop();

        if(vu[cur][pass][crois])
            continue;
        vu[cur][pass][crois] = 1;
        reponse[cur][pass][crois] = curDist;

        for(auto voisin : adj[cur]) {
            if(pass == 2) {
                q.push({voisin.dest, curDist + voisin.cost, pass, crois});
            }
            else if(pass == 0) {
                q.push({voisin.dest, curDist + voisin.cost, sommetPcc[voisin.dest], crois});
            }
            else {
                if(sommetPcc[voisin.dest] && correct(dist[cur], dist[voisin.dest], crois)) {
                    q.push({voisin.dest, curDist, 1, crois});
                }
                else {
                    q.push({voisin.dest, curDist + voisin.cost, 2, crois});
                }
            }
        }
    }
}

signed main() {
    input();
    calcPcc();
    calcRep();

    int rep = INF;

    for(int i = 0; i < 3; i++) {
        rep = min(rep, min(reponse[arrive][i][0], reponse[arrive][i][1]));
    }

    if(rep == INF) {
        cout << -1;
        return 0;
    }
        

    cout << rep;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void calcRep()':
commuter_pass.cpp:116:67: warning: narrowing conversion of 'crois' from 'long long int' to 'bool' [-Wnarrowing]
  116 |                 q.push({voisin.dest, curDist + voisin.cost, pass, crois});
      |                                                                   ^~~~~
commuter_pass.cpp:119:85: warning: narrowing conversion of 'crois' from 'long long int' to 'bool' [-Wnarrowing]
  119 |                 q.push({voisin.dest, curDist + voisin.cost, sommetPcc[voisin.dest], crois});
      |                                                                                     ^~~~~
commuter_pass.cpp:123:54: warning: narrowing conversion of 'crois' from 'long long int' to 'bool' [-Wnarrowing]
  123 |                     q.push({voisin.dest, curDist, 1, crois});
      |                                                      ^~~~~
commuter_pass.cpp:126:68: warning: narrowing conversion of 'crois' from 'long long int' to 'bool' [-Wnarrowing]
  126 |                     q.push({voisin.dest, curDist + voisin.cost, 2, crois});
      |                                                                    ^~~~~

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