제출 #698186

#제출 시각아이디문제언어결과실행 시간메모리
698186RichemCommuter Pass (JOI18_commuter_pass)C++14
15 / 100
709 ms31784 KiB
#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}); } } int prof[MAX_SOMMET] = {0}; bool vu[MAX_SOMMET][4] = {0}; int ordre[MAX_SOMMET] = {0}; int dist[MAX_SOMMET]; bool vuOrdre[MAX_SOMMET] = {0}; void calcOrdre(int sommet, int curOrdre) { if(vuOrdre[sommet]) { return; } vuOrdre[sommet] = 1; ordre[sommet] = curOrdre; for(auto voisin : adj[sommet]) { if(dist[sommet] == dist[voisin.dest] + voisin.cost) { calcOrdre(voisin.dest, curOrdre+1); } } } 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; if(ordre[deb] == 0) { q.push({deb, 0, 0}); } else { 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(ordre[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, 1}); q.push({voisin.dest, cur.dist + voisin.cost, 2}); } if(cur.type == 1 && ordre[cur.sommet] + 1 == ordre[voisin.dest]) { q.push({voisin.dest, cur.dist, 1}); } if(cur.type == 2 && ordre[cur.sommet] == ordre[voisin.dest] + 1) { q.push({voisin.dest, cur.dist, 2}); } q.push({voisin.dest, cur.dist + voisin.cost, 3}); } } } } signed main() { input(); pcc(debOpti, finOpti); calcOrdre(finOpti, 1); pcc(debReq, finReq); cout << rep; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...