제출 #968419

#제출 시각아이디문제언어결과실행 시간메모리
968419saayan007사이버랜드 (APIO23_cyberland)C++17
44 / 100
35 ms9348 KiB
#include "bits/stdc++.h" #include "cyberland.h" using namespace std; #include <vector> double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { vector<pair<int, double>> adj[N]; for(int i = 0; i < M; ++i) { adj[x[i]].emplace_back(y[i], c[i]); adj[y[i]].emplace_back(x[i], c[i]); } double dist[N]; for(int i = 0; i < N; ++i) dist[i] = -1; dist[0] = 0; // bfs 1 queue<int> pq; bool vis[N] = {}; vis[0] = 1; pq.push(0); while(!pq.empty()) { int a = pq.front(); pq.pop(); if(a == H) continue; if(arr[a] == 0) { dist[a] = 0; } for(auto [b, w] : adj[a]) { if(vis[b]) continue; vis[b] = 1; pq.push(b); } } // bfs 1 ends queue<int> q; for(int i = 0; i < N; ++i) if(dist[i] == 0) q.push(i); while(!q.empty()) { int a = q.front(); q.pop(); for(auto [b, w] : adj[a]) { if(dist[b] == -1 || dist[b] > dist[a] + w) { dist[b] = dist[a] + w; q.push(b); } } } return dist[H]; /* vector<pair<int, double>> adj[N]; */ /* for(int i = 0; i < M; ++i) { */ /* adj[x[i]].emplace_back(y[i], c[i]); */ /* adj[y[i]].emplace_back(x[i], c[i]); */ /* } */ /* double dist[N]; */ /* for(int i = 0; i < N; ++i) dist[i] = -1; */ // there's a pq declared earlier as well /* priority_queue<pair<double, int>> pq; */ /* for(int i = 1; i < N; ++i) { */ /* if(arr[i] == 0 || i == 0) { */ /* dist[i] = 0; */ /* pq.emplace(-dist[i], i); */ /* } */ /* } */ /* while(!pq.empty()) { */ /* int a = pq.top().second; */ /* double d = -pq.top().first; */ /* pq.pop(); */ /* if(dist[a] < d || a == H) { */ /* continue; */ /* } */ /* for(auto [b, w] : adj[a]) { */ /* if(dist[b] == -1 || d + w < dist[b]) { */ /* dist[b] = d + w; */ /* pq.emplace(-dist[b], b); */ /* } */ /* } */ /* } */ /* return dist[H]; */ }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...