# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
864535 | 2023-10-23T07:31:37 Z | maks007 | Toll (BOI17_toll) | C++14 | 0 ms | 0 KB |
// Bismi ALlah #include "bits/stdc++.h" using namespace std; signed main () { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m, k, query; cin >> k >> n >> m >> query; vector<pair <int,int>> g[n]; for(int i = 0; i < m; i ++) { int u, v; cin >> u >> v; int w; cin >> w; g[u].push_back({v, w}); } int dp[n]; while(query --) { int a, b; cin >> a >> b; for(int i = 0; i < n; i ++) dp[i] = 1e9; dp[b] = 0; for(int i = n - 1; i >= 0; i--) { if(dp[i] != 1e9) { for(auto [u, w] : revG[i]) { dp[u] = min(dp[u], dp[i] + w); } } } if(dp[a] == 1e9) cout << -1 << "\n"; else cout << dp[a] << "\n"; } return 0; }