fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int> dijkstra(vector<vector<pair<int,int>>>& adj, int source, int target) {
  5.     int n = adj.size();
  6.     priority_queue<pair<int,int>> q;
  7.     vector<int> distance(n, INT64_MAX);
  8.     vector<bool> visit(n, false);
  9.     distance[source] = 0;
  10.     q.push({0, source});
  11.     while (!q.empty()) {
  12.         int a = q.top().second;
  13.         q.pop();
  14.         if (!visit[a]) {
  15.             visit[a] = true;
  16.             for (auto u: adj[a]) {
  17.                 int b = u.first, w = u.second;
  18.                 distance[b] = min(distance[b], distance[a]+w);
  19.                 q.push({-distance[b], b});
  20.             }
  21.         }
  22.     }
  23.     return distance;
  24. }
  25.  
  26. int main() {
  27.  
  28.     ios_base::sync_with_stdio(false);
  29.     cin.tie(NULL);
  30.  
  31.     #ifndef ONLINE_JUDGE 
  32.         freopen("in", "r", stdin);  
  33.     #endif
  34.  
  35.     int t;
  36.     cin >> t;
  37.     while (t--) {
  38.         int n, e;
  39.         cin >> n >> e;
  40.         vector<vector<pair<int,int>>> adj(n+1);
  41.         for (int i=0; i<e; i++) {
  42.             int x, y, z;
  43.             cin >> x >> y >> z;
  44.             adj[x].push_back({y, z});
  45.         }
  46.         int source, target;
  47.         cin >> source >> target;
  48.         vector<int> res = dijkstra(adj, source, target);
  49.         if (res[n] < INT64_MAX) {
  50.             cout << res[n] << '\n';
  51.         } else {
  52.             cout << "NO\n";
  53.         }
  54.     }
  55.  
  56.  
  57.  
  58.     return 0;
  59. }
  60.  
Success #stdin #stdout 0s 4732KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1QIxH2
problem EZDIJKST, based on SPOJ submission 27300067 (CPP14-CLANG), 2021-01-19 07:01:01
language:
C++14 (clang 8.0)
created:
3 years ago
visibility:
secret

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!