Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- // tiom4eg's precompiler options
- // POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
- // IO settings
- #define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
- // Quick types
- #define ll long long
- #define ull unsigned long long
- #define pii pair <int, int>
- #define vi vector <int>
- #define mi vector <vector <int> >
- // Segment tree
- #define lp(x) (x + 1) >> 1
- #define rp(x) (x - 1) >> 1
- #define lk(x) x << 1
- #define rk(x) (x << 1) + 1
- // Quick functions
- #define endl "\n"
- #define F first
- #define S second
- #define all(a) a.begin(), a.end()
- #define pb push_back
- #define mp make_pair
- #define fint(n) int n; cin >> n
- #define fstr(s) string s; cin >> s
- #define farr(a, n) int a[n]; for (int pog = 0; pog < n; ++pog) cin >> a[pog]
- #define fprint(s) cout << s << endl
- #define ffprint(s) fout << s << endl
- #define bback(a) a[a.size() - 1]
- #define arrprint(a) for (int lol = 0; lol < a.size(); ++lol) cout << a[lol] << ' ';
- #define farrprint(a) for (int kek = 0; kek < a.size(); ++kek) fout << a[kek] << ' ';
- // Quick fors
- #define FOR1(s, n) for (int i = s; i < n; ++i)
- #define FOR2(s, n) for (int j = s; j < n; ++j)
- #define FOR3(s, n) for (int k = s; k < n; ++k)
- #define RFOR(n, s) for (int l = n; l >= s; --l)
- // Pragmas
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC target("avx,fma")
- // POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
- using namespace std;
- int main() {
- fastIO;
- int n, m, k; cin >> n >> m >> k;
- vector <pii> g[n];
- FOR1(0, m) {
- int a, b, t; cin >> a >> b >> t;
- a--, b--;
- g[a].pb({b, t});
- g[b].pb({a, t});
- }
- int d[n]; FOR1(0, n - 1) d[i] = 1e9;
- d[n - 1] = 0;
- for (int iter = 0; iter < n; ++iter) { // Iterations
- FOR1(0, n) { // Begins
- vector <pii> current;
- for (auto p : g[i]) current.pb({d[p.F] + p.S, p.S});
- sort(all(current));
- for (int l = 0; l < min(k, (int)current.size()); ++l) d[i] = min(d[i], current[l].F + current[l].S);
- if ((int)current.size() > k) d[i] = min(d[i], current[k].F);
- }
- }
- if (d[0] < 1e9) cout << d[0];
- else cout << -1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement