제출 #714642

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
714642		parsadox2	Toll (BOI17_toll)	C++14	100 / 100	197 ms	27852 KiB

toll

#include <bits/stdc++.h>
#define pb 		push_back
#define F		first
#define S 		second
#define debug(x)    cout << #x << "= " << x << ", "
#define ll 		long long
#define fast 		ios::sync_with_stdio(false), cin.tie(0),  cout.tie(0)
#define SZ(x)         (int) x.size()
#define wall 		cout << endl;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 5e4 + 10 , maxl = 17 , maxk = 7 , inf = 1e9;
int n, m , q , k , dis[maxn][maxl][maxk];
vector <pair<int , int>> adj[maxn];

int find_nex(int v , int jmp , int ps)
{
	int now = v / k;
	int to = now + (1 << jmp);
	to *= k;
	to += ps;
	return min(to , n);
}

int Find_ans(int nb , int np , int fb , int fp)
{
	int res[2][maxk];
	for(int i = 0 ; i < k ; i++)  res[0][i] = res[1][i] = inf;
	res[0][np] = 0;
	int l = nb * k , fbi = (fb - nb) , upd = 0 , val = fb - nb;
	for(int jmp = 0 ; jmp < maxl ; jmp++)  if((val >> jmp) & 1)
	{
		for(int i = 0 ; i < k ; i++)  res[upd ^ 1][i] = inf;
		
		for(int from = 0 ; from < k ; from++)
		{
			int v = l + from;
			for(int to = 0 ; to < k ; to++)
			{
				res[upd ^ 1][to] = min(res[upd ^ 1][to] , res[upd][from] + dis[v][jmp][to]);
			}
		}
		nb += (1 << jmp);
		l = nb * k;
		upd ^= 1;
	}
	return (res[upd][fp] == inf ? -1 : res[upd][fp]);
}

int32_t main()
{
	fast;
	cin >> k >> n >> m >> q;
	for(int i = 0 ; i < maxn ; i++)
		for(int j = 0 ; j < maxl ; j++)
			for(int k = 0 ; k < maxk ; k++)
				dis[i][j][k] = inf;

	for(int i = 0 ; i < m ; i++)
	{
		int v , u , c;  cin >> v >> u >> c;
		adj[v].pb({u , c});
		dis[v][0][(u % k)] = c;
	}
	for(int jmp = 1 ; jmp < maxl ; jmp++)
		for(int v = 0 ; v < n ; v++)
			for(int from = 0 ; from < k ; from++)
				for(int to = 0 ; to < k ; to++)  
					dis[v][jmp][to] = min(dis[v][jmp][to] , dis[v][jmp - 1][from] + dis[find_nex(v , jmp - 1 , from)][jmp - 1][to]);
	while(q--)
	{
		int v , u;  cin >> v >> u;
		if(v / k >= u / k)
		{
			cout << -1 << '\n';
			continue;
		}
		cout << Find_ans(v / k , v % k , u / k , u % k) << '\n';
	}
	return 0;

}

컴파일 시 표준 에러 (stderr) 메시지

toll.cpp: In function 'int Find_ans(int, int, int, int)':
toll.cpp:31:19: warning: unused variable 'fbi' [-Wunused-variable]
   31 |  int l = nb * k , fbi = (fb - nb) , upd = 0 , val = fb - nb;
      |                   ^~~

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