fork download 
  1. #include <bits/stdc++.h>
  2. #ifndef ONLINE_JUDGE
  3. #include "debug.h"
  4. #else
  5. #define debug(...)
  6. #endif
  7. #define int long long
  8. #define pep_Guardiola      \
  9.   ios::sync_with_stdio(0); \
  10.   cin.tie(0);              \
  11.   cout.tie(0);
  12. using namespace std;
  13. void io()
  14. {
  15. #ifndef ONLINE_JUDGE
  16.   freopen("input.txt", "r", stdin);
  17.   // freopen("output.txt", "w", stdout);
  18. #endif
  19. }
  20. const int inf = 1e16;
  21. signed main()
  22. {
  23.   pep_Guardiola
  24.   io();
  25.   int n, m, k;
  26.   cin >> n >> m >> k;
  27.   vector<vector<pair<int, int>>> adj(n + 1);
  28.   for (int i = 0; i < m; i++)
  29.   {
  30.     int u, v, w;
  31.     cin >> u >> v >> w;
  32.     adj[u].push_back({v, w});
  33.   }
  34.   vector<vector<int>> dist(n + 1, vector<int>(k, inf));
  35.   dist[1][0] = 0;
  36.   priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
  37.   pq.push({0, 1});
  38.   while (pq.size())
  39.   {
  40.     auto [d, u] = pq.top();
  41.     pq.pop();
  42.     sort(dist[u].begin(), dist[u].end());
  43.     if (d > dist[u][k - 1])
  44.       continue;
  45.     for (auto [v, w] : adj[u])
  46.     {
  47.       sort(dist[v].begin(), dist[v].end());
  48.       if (dist[v][k - 1] > w + d)
  49.       {
  50.         dist[v][k - 1] = w + d;
  51.         pq.push({w + d, v});
  52.       }
  53.     }
  54.   }
  55.   sort(dist[n].begin(), dist[n].end());
  56.   for (auto &i : dist[n])
  57.     cout << i << " ";
  58. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
4 6 3
1 2 1
1 3 3
2 3 2
2 4 6
3 2 8
3 4 1
stdout 
4 4 7
https://ideone.com/FMlH1i
language:
C++ (gcc 8.3)
created:
23 hours 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!