fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX_N = 1e4+5;
  5. const int inf = 1e9;
  6.  
  7. int n, m;
  8. // krawedz to para (wierzcholek_docelowy, waga_krawedzi)
  9. vector<pair<int, int>> G[MAX_N];
  10. int dist[MAX_N];
  11.  
  12. void solve() {
  13.     cin >> n >> m;
  14.  
  15.     // czyszczenie po poprzednim tescie
  16.     for (int i = 1; i <= n; i++) {
  17.         G[i].clear();
  18.         dist[i] = inf;
  19.     }
  20.  
  21.     for (int i = 0; i < m; i++) {
  22.         int a, b, c;
  23.         cin >> a >> b >> c;
  24.         G[a].push_back(make_pair(b, c));
  25.     }
  26.  
  27.     int start, meta;
  28.     cin >> start >> meta;
  29.  
  30.     // przechowujemy pary (odleglosc_od_startu, nr_wierzcholka)
  31.     multiset<pair<int, int>> S;
  32.  
  33.     S.insert(make_pair(0, start));
  34.  
  35.     while (!S.empty()) {
  36.         pair<int, int> tmp = *S.begin();
  37.         S.erase(S.begin());
  38.  
  39.         int curDist = tmp.first;
  40.         int v = tmp.second;
  41.  
  42.         for (pair<int, int> e: G[v]) {
  43.             int to = e.first;
  44.             int cost = e.second;
  45.  
  46.             if (curDist + cost < dist[to]) {
  47.                 dist[to] = curDist + cost;
  48.                 S.insert(make_pair(dist[to], to));
  49.             }
  50.         }
  51.     }
  52.  
  53.     if (dist[meta] == inf) {
  54.         cout << "NIE\n";
  55.     } else {
  56.         cout << dist[meta] << '\n';
  57.     }
  58. }
  59.  
  60.  
  61.  
  62. int main() {
  63.     ios_base::sync_with_stdio(0);
  64.     cin.tie(0);
  65.  
  66.     int T;
  67.     cin >> T;
  68.     for (int i = 0; i < T; i++) {
  69.         solve();
  70.     }
  71.  
  72.  
  73.     return 0;
  74. }
  75.  
Success #stdin #stdout 0.01s 5408KB
comments (?)
stdin
copy 
3
3 2
1 2 5
2 3 7
1 3
3 3
1 2 4
1 3 7
2 3 1
1 3
3 1
1 2 4
1 3
stdout
copy 
12
5
NIE
https://ideone.com/A8fLdt
language:
C++14 (gcc 8.3)
created:
1 year 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!