Advertisement
tiom4eg

Untitled

Nov 6th, 2021
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.20 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. // tiom4eg's precompiler options
  3. // POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
  4. // IO settings
  5. #define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
  6. // Quick types
  7. #define ll long long
  8. #define ull unsigned long long
  9. #define pii pair <int, int>
  10. #define vi vector <int>
  11. #define mi vector <vector <int> >
  12. // Segment tree
  13. #define lp(x) (x + 1) >> 1
  14. #define rp(x) (x - 1) >> 1
  15. #define lk(x) x << 1
  16. #define rk(x) (x << 1) + 1
  17. // Quick functions
  18. #define endl "\n"
  19. #define F first
  20. #define S second
  21. #define all(a) a.begin(), a.end()
  22. #define pb push_back
  23. #define mp make_pair
  24. #define fint(n) int n; cin >> n
  25. #define fstr(s) string s; cin >> s
  26. #define farr(a, n) int a[n]; for (int pog = 0; pog < n; ++pog) cin >> a[pog]
  27. #define fprint(s) cout << s << endl
  28. #define ffprint(s) fout << s << endl
  29. #define bback(a) a[a.size() - 1]
  30. #define arrprint(a) for (int lol = 0; lol < a.size(); ++lol) cout << a[lol] << ' ';
  31. #define farrprint(a) for (int kek = 0; kek < a.size(); ++kek) fout << a[kek] << ' ';
  32. // Quick fors
  33. #define FOR1(s, n) for (int i = s; i < n; ++i)
  34. #define FOR2(s, n) for (int j = s; j < n; ++j)
  35. #define FOR3(s, n) for (int k = s; k < n; ++k)
  36. #define RFOR(n, s) for (int l = n; l >= s; --l)
  37. // Pragmas
  38. #pragma GCC optimize("Ofast")
  39. #pragma GCC optimize("unroll-loops")
  40. #pragma GCC target("avx,fma")
  41. // POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
  42. using namespace std;
  43.  
  44. int main() {
  45. fastIO;
  46. int n, m, k; cin >> n >> m >> k;
  47. vector <pii> g[n];
  48. FOR1(0, m) {
  49. int a, b, t; cin >> a >> b >> t;
  50. a--, b--;
  51. g[a].pb({b, t});
  52. g[b].pb({a, t});
  53. }
  54. int d[n]; FOR1(0, n - 1) d[i] = 1e9;
  55. d[n - 1] = 0;
  56. for (int iter = 0; iter < n; ++iter) { // Iterations
  57. FOR1(0, n) { // Begins
  58. vector <pii> current;
  59. for (auto p : g[i]) current.pb({d[p.F] + p.S, p.S});
  60. sort(all(current));
  61. for (int l = 0; l < min(k, (int)current.size()); ++l) d[i] = min(d[i], current[l].F + current[l].S);
  62. if ((int)current.size() > k) d[i] = min(d[i], current[k].F);
  63. }
  64. }
  65. if (d[0] < 1e9) cout << d[0];
  66. else cout << -1;
  67. }
  68.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement