Submission #533478

#TimeUsernameProblemLanguageResultExecution timeMemory
533478SlavitaAutobus (COCI22_autobus)C++14
15 / 70
1084 ms1108 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> #define ve vector<int> #define pb push_back #define mp make_pair #define fi first #define se second #define pi pair<int,int> #define all(v) v.begin(),v.end() #define si(v) (int)v.size() #define en '\n' #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> #define ordered_muiltiset tree<int, null_type,less_equal<>, rb_tree_tag,tree_order_statistics_node_update> //#define int long long using namespace std; //using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; const int N = 1e3 + 228; const int big = 1e9 + 228; const ll llbig = 1e18 + 228; //ordered_set os; // os.order_of_key(4), (*os.find_by_order(5)) ll n, m, ans, k, q, d[N][N], mem[N][N]; priority_queue<pair<pair<ll, ll>, ll>> Q; //#undef int int main(){ //#define int long long iostream::sync_with_stdio(false); cin.tie(0); ios_base::sync_with_stdio(false); cout.tie(0); //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); cin >> n >> m; for (int i = 1; i <= m; i++){ ll a, b, t; cin >> a >> b >> t; if (mem[a][b] == 0) mem[a][b] = t; else mem[a][b] = min(mem[a][b], t); } cin >> k >> q; while(q--){ ll start, finish; cin >> start >> finish; Q.push({{0, 0}, start}); for (int i = 1; i <= n; i++) for (int j = 0; j <= n; j++) d[i][j] = llbig; d[start][0] = 0; while(!Q.empty()){ ll v = Q.top().se; ll time = -Q.top().fi.fi; ll kol = -Q.top().fi.se; Q.pop(); if (kol > k) {continue;} for (int u = 1; u <= n; u++){ ll c = mem[v][u]; if (!c) continue; if (d[u][kol + 1] < time + c) continue; d[u][kol + 1] = time + c; Q.push({{-time-c, -kol-1}, u}); } } ll mn = llbig; for (int i = 0; i <= k; i++) mn = min(mn, d[finish][i]); cout << (mn == llbig ? -1 : mn) << en; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...