Submission #674609

#	Time	Username	Problem	Language	Result	Execution time	Memory
674609		esomer	Toll (BOI17_toll)	C++17	100 / 100	1219 ms	12480 KiB

toll

#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define endl "\n"
 
const int MOD = 998244353;

void solve(){
	int n, o, k, m; cin >> k >> n >> m >> o;
	vector<vector<pair<int, int>>> adj(n);
	for(int i = 0; i < m; i++){
		int a, b, t; cin >> a >> b >> t;
		adj[a].push_back({b, t});
	}
	int groups = (n - 1) / k + 1;
	int sqr = sqrt(groups);
	vector<vector<int>> calc(n, vector<int> (k, 1e17));
	for(int i = 0; i < groups; i += sqr){
		for(int j = i * k; j < (i + 1) * k && j < n; j++){
			queue<int> q;
			q.push(j);
			map<int, int> d; d[j] = 0;
			while(!q.empty()){
				int x = q.front(); q.pop();
				if(x / k == i + sqr){
					calc[j][x % k] = d[x];
					continue;
				}
				if((x / k) % sqr != 0){
					calc[x][j % k] = d[x];
				}
				for(auto p : adj[x]){
					int node = p.first;
					bool gd = d.count(node);
					if(!gd) {d[node] = d[x] + p.second; q.push(node);}
					else d[node] = min(d[node], d[x] + p.second);
				}
			}
		}
	}
	while(o--){
		int a, b; cin >> a >> b;
		if(a / k >= b / k){
			cout << -1 << endl;
			continue;
		}
		queue<int> q;
		q.push(a);
		map<int, int> d; d[a] = 0;
		vector<int> dist(k, 1e17);
		int gr = -1;
		bool done = 0;
		while(!q.empty()){
			int x = q.front(); q.pop();
			if(done) continue;
			if((x / k) % sqr == 0){
				gr = x / k;
				dist[x % k] = d[x];
				continue;
			}
			if(x == b){
				cout << d[x] << endl;
				done = 1;
				continue;
			}
			for(auto p : adj[x]){
				int node = p.first;
				bool gd = d.count(node);
				if(!gd) {d[node] = d[x] + p.second; q.push(node);}
				else d[node] = min(d[node], d[x] + p.second);
			}
		}
		if(done) continue;
		if(b / k < gr){
			cout << -1 << endl;
			continue;
		}
		if(gr == -1){
			cout << -1 << endl;
			continue;
		}
		while((gr + sqr) * k <= b){
			vector<int> nw(k, 1e17);
			for(int i = 0; i < k && gr * k + i < n; i++){
				for(int j = 0; j < k; j++){
					nw[j] = min(nw[j], dist[i] + calc[gr * k + i][j]);
				}
			}
			dist = nw;
			gr += sqr;
		}
		if((b / k) % sqr == 0) cout << (dist[b % k] >= 1e10 ? -1 : dist[b % k]) << endl;
		else{
			int ans = 1e17;
			for(int i = 0; i < k; i++){
				ans = min(ans, dist[i] + calc[b][i]);
			}
			if(ans >= 1e10) cout << -1 << endl;
			else cout << ans << endl;
		}
	}
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    //freopen("inpt.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
 
    //int tt; cin >> tt;
    int tt = 1;
    for(int t = 1; t <= tt; t++){
        solve();
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44