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. typedef vector<vector<pii>> Graph;
  10.  
  11. void dijkstra(const Graph& graph, int start, vector<int>& dist) {
  12.     priority_queue<pii, vector<pii>, greater<pii>> pq;
  13.     pq.push({0, start});
  14.     dist[start] = 0;
  15.  
  16.     while (!pq.empty()) {
  17.         int u = pq.top().second;
  18.         pq.pop();
  19.  
  20.         for (const auto& edge : graph[u]) {
  21.             int v = edge.first;
  22.             int w = edge.second;
  23.  
  24.             if (dist[v] > dist[u] + w) {
  25.                 dist[v] = dist[u] + w;
  26.                 pq.push({dist[v], v});
  27.             }
  28.         }
  29.     }
  30. }
  31.  
  32. int main() {
  33.     int n, m;
  34.     cin >> n >> m;
  35.  
  36.     Graph graph(n);
  37.     for (int i = 0; i < m; i++) {
  38.         int u, v, w;
  39.         cin >> u >> v >> w;
  40.         graph[u].push_back({v, w});
  41.         graph[v].push_back({u, w});
  42.     }
  43.  
  44.     int start, end;
  45.     cin >> start >> end;
  46.  
  47.     vector<int> dist(n, INT_MAX);
  48.     dijkstra(graph, start, dist);
  49.  
  50.     cout << "Il cammino piu' breve da " << start << " a " << end << " e' " << dist[end] << endl;
  51.  
  52.     return 0;
  53. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
4 5
0 1 1
0 2 2
1 3 1
2 1 3
2 3 5
stdout
copy 
Il cammino piu' breve da 3 a 5 e' 0
https://ideone.com/tENScP
language:
C++ (gcc 8.3)
created:
2 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!