Submission #714560

#TimeUsernameProblemLanguageResultExecution timeMemory
714560faribourzToll (BOI17_toll)C++14
18 / 100
3056 ms5620 KiB
// Only GOD // Believe in yourself! // -o Sango zadam be shishe // -o Comeback bezan hamishe! #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; #define pb push_back #define F first #define S second #define bit(x, y) (x >> y)&1 #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() #define kill(x) return cout << x << '\n', void() #define KILL(x) return cout << x << '\n', 0 #define mid ((l+r)>>1) #define lid (id << 1) #define rid (lid | 1) const int N = 5e4+10; const int INF = 1e9+10; int n, m, k, o; vector<pii> query[N]; vector<pii> G[N]; int ans[N], dis[N]; set<int> s; void dij(int v){ priority_queue<pii> q; for(int i=0; i <= n; i++) dis[i] = INF; dis[v] = 0; q.push({0, v}); while(!q.empty()){ int a=q.top().S; q.pop(); for(auto x : G[a]){ if(dis[a] + x.S < dis[x.F]){ dis[x.F] = dis[a] + x.S; q.push({-dis[x.F], x.F}); } } } } int32_t main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> k >> n >> m >> o; for(int i = 0; i < m; i++){ int v, u, w; cin >> v >> u >> w; G[v].pb({u, w}); } for(int i =1 ; i <= o; i++){ int v, u; cin >> v >> u; query[v].pb({u, i}); s.insert(v); } for(int u:s){ dij(u); for(auto x : query[u]){ ans[x.S] = dis[x.F]; } } for(int i = 1;i <= o; i++) cout << (ans[i] == INF ? -1 : ans[i]) << '\n'; }
#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...