Submission #245191

#TimeUsernameProblemLanguageResultExecution timeMemory
245191Tc14Toll (BOI17_toll)C++17
7 / 100
64 ms5880 KiB
//#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define ve vector typedef long long ll; int C; ve<ve<pair<int, int>>> G; ve<int> Comp, D; void dfs(int u, int d, int c) { int v, t; Comp[u] = c; D[u] = d; for (pair<int, int> e : G[u]) { tie(v, t) = e; if (Comp[v] == 0) dfs(v, d + t, c); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int k, n, m, o, a, b, t; cin >> k >> n >> m >> o; G = ve<ve<pair<int, int>>>(n); Comp = ve<int>(n); D = ve<int>(n); for (int i = 0; i < m; i++) { cin >> a >> b >> t; G[a].push_back({b, t}); } C = 0; for (int i = 0; i < n; i++) { if (Comp[i] == 0) { C++; dfs(i, 0, C); } } for (int i = 0; i < o; i++) { cin >> a >> b; if (Comp[a] == Comp[b]) { if (b >= a) cout << D[b] - D[a] << endl; else cout << -1 << endl; } else cout << -1 << endl; } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...