Submission #1359306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1359306		jump	Sightseeing (NOI14_sightseeing)	C++20	25 / 25	1302 ms	164264 KiB

sightseeing

#include <bits/stdc++.h>

int v,e,q;
int dist[500010];
std::vector<std::pair<int,int>> adj[500010];
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> v >> e >> q;
  for(int i=1;i<=e;i++){
    int a,b,w;
    std::cin >> a >> b >> w;
    adj[a].push_back({b,w});
    adj[b].push_back({a,w});
  }
  std::priority_queue<std::pair<int,int>> pq;
  pq.push({1e18,1});
  dist[1]=1e18;
  while(!pq.empty()){
    int qual = pq.top().first;
    int node = pq.top().second;
    pq.pop();
    for(auto [to,parq]:adj[node]){
      if(dist[to]<std::min(parq,qual)){
        dist[to]=std::min(parq,qual);
        pq.push({dist[to],to});
      }
    }
  }
  while(q--){
    int ask;
    std::cin >> ask;
    std::cout << dist[ask] << '\n';
  }
}

Compilation message (stderr)

sightseeing.cpp: In function 'int main()':
sightseeing.cpp:18:11: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   18 |   dist[1]=1e18;
      |           ^~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 10 / 10