제출 #1314664

#제출 시각아이디문제언어결과실행 시간메모리
1314664joshjuiceSightseeing (NOI14_sightseeing)C++20
25 / 25
2352 ms163992 KiB
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

vector<int> widest_path(int src, const vector<vector<pii>>& adj) {
    int V = adj.size() - 1;
    const int NEG_INF = -1;
    vector<int> best(V+1, NEG_INF);
    best[src] = INT_MAX;
    priority_queue<pii> pq;
    pq.emplace(best[src], src);
    while (!pq.empty()) {
        auto [q, u] = pq.top(); 
        pq.pop();
        if (q < best[u]) continue;
        for (auto& [v, w] : adj[u]) {
            int alt = min(q, w);
            if (alt > best[v]) {
                best[v] = alt;
                pq.push({best[v], v});
            }
        }
    }
    return best;
}


int main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int n, e, q; cin >> n >> e >> q;
  vector<vector<pii>> adj(n+1);
  while (e--) {
    int x, y, w; cin >> x >> y >> w;
    adj[x].emplace_back(y, w);
    adj[y].emplace_back(x, w);
  }
  vector<int> dist = widest_path(1, adj);
  while (q--) {
    int x; cin >> x;
    cout << dist[x] << '\n';
  }
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...