Submission #696741

#	Time	Username	Problem	Language	Result	Execution time	Memory
696741		vjudge1	Toll (BOI17_toll)	C++17	0 / 100	3054 ms	8168 KiB

toll

#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pii;
#define fi first
#define se second
#define gcd __gcd
#define endl '\n'
const int N=200050,M=1000000007;
const ll INF=0x3f3f3f3f3f3f3f3f;

ll k, n, m, q, a, b, t;
map<pii, ll> w;

ll len(ll a, ll b){
	ll res[k], tmp[k], x=a/k, xe=b/k, p=x*k;
	for(ll i=0; i<k; i++){
		res[i]=tmp[i]=INF;
		if(w[{a, p+k+i}]){ 
		res[i]=w[{a, p+k+i}];
		}
	}
	p+=k;
	while(p/k<xe){
		for(ll i=0; i<k; i++){
			for(ll j=0; j<k; j++){
				if(res[i] && w[{p+i, p+k+j}]) 
					tmp[j]=min(tmp[j], res[i]+w[{p+i, p+k+j}]);
			}
		}
		for(ll i=0; i<k; i++) res[i]=tmp[i];
		p+=k;
	}
	return res[b%k]==INF? -1: res[b%k];
}

signed main(){
	ios_base::sync_with_stdio(NULL); 
	cin.tie(nullptr); cout.tie(nullptr);
	cin>>k>>n>>m>>q;
	while(m--){
		cin>>a>>b>>t;
		if(a>b) swap(a, b);
		// cout<<a<<" "<<b<<" ";
		w[{a, b}]=t;
		// cout<<w[{a, b}]<<endl;
	}
	while(q--){
		cin>>a>>b;
		cout<<len(a, b)<<endl;
	}
    return 0;
}	

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