제출 #485369

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
485369		Richem	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	745 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, 0, 0});
    q.push({depart, 0, 0, 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(correct(dist[cur], dist[voisin.dest], crois) && sommetPcc[voisin.dest] == voisin.cost && pass != 2) {
                q.push({voisin.dest, curDist, 1, crois});
            }
            if(!sommetPcc[voisin.dest]) {
                q.push({voisin.dest, curDist + voisin.cost, (pass > 0) * 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]));
    }

    cout << rep;
}

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp: In function 'void calcRep()':
commuter_pass.cpp:116:50: warning: narrowing conversion of 'crois' from 'long long int' to 'bool' [-Wnarrowing]
  116 |                 q.push({voisin.dest, curDist, 1, crois});
      |                                                  ^~~~~
commuter_pass.cpp:119:77: warning: narrowing conversion of 'crois' from 'long long int' to 'bool' [-Wnarrowing]
  119 |                 q.push({voisin.dest, curDist + voisin.cost, (pass > 0) * 2, crois});
      |                                                                             ^~~~~

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