fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <climits>
  5.  
  6. using namespace std;
  7.  
  8. typedef pair<int, int> pii;
  9.  
  10. const int INF = INT_MAX;
  11.  
  12. vector<vector<pii>> graph;
  13.  
  14. int findHighestSafeRoute(int n) {
  15.     vector<int> dist(n + 1, INF);
  16.     priority_queue<pii, vector<pii>, greater<pii>> pq;
  17.  
  18.     pq.push(make_pair(0, 1));
  19.     dist[1] = 0;
  20.  
  21.     while (!pq.empty()) {
  22.         int u = pq.top().second;
  23.         int danger = pq.top().first;
  24.         pq.pop();
  25.  
  26.         if (danger > dist[u]) {
  27.             continue;
  28.         }
  29.  
  30.         for (pii edge : graph[u]) {
  31.             int v = edge.first;
  32.             int roadDanger = edge.second;
  33.  
  34.             if (dist[u] + roadDanger < dist[v]) {
  35.                 dist[v] = dist[u] + roadDanger;
  36.                 pq.push(make_pair(dist[v], v));
  37.             }
  38.         }
  39.     }
  40.  
  41.     int highestDanger = 0;
  42.     for (int i = 1; i <= n; i++) {
  43.         highestDanger = max(highestDanger, dist[i]);
  44.     }
  45.  
  46.     return highestDanger;
  47. }
  48.  
  49. int main() {
  50.     int n, m;
  51.     cin >> n >> m;
  52.  
  53.     graph.resize(n + 1);
  54.  
  55.     for (int i = 0; i < m; i++) {
  56.         int a, b, c;
  57.         cin >> a >> b >> c;
  58.         graph[a].push_back(make_pair(b, c));
  59.         graph[b].push_back(make_pair(a, c));
  60.     }
  61.  
  62.     int highestDanger = findHighestSafeRoute(n);
  63.     cout << highestDanger << endl;
  64.  
  65.     return 0;
  66. }
  67.  
Success #stdin #stdout 0.01s 5516KB
comments (?)
stdin
copy 
3 2
1 2 1
2 3 1
stdout
copy 
2
https://ideone.com/NU90Lu
language:
C++ (gcc 8.3)
created:
317 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!