제출 #450411

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
450411		snoop	Toll (BOI17_toll)	C++14	0 / 100	115 ms	22764 KiB

toll

#include<bits/stdc++.h>
#include<math.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N = 5e4 + 5, oo = 1e18;
int t, dist[N][5][5], d[N][5][5], n, k, m, q, ans[N];
vector<int> cur[N];
pair<int, int> p[N];
void solve(int l, int r, vector<int> v) {
	if (l == r) return;
	int mid = (l + r) / 2;
	vector<int> x, y;
	for (int i = l; i <= r; i++) cur[i].clear();
	for (int i = 0; i < v.size(); i++) {
		int ind = v[i];
		if (p[ind].s / k <= mid) x.push_back(v[i]);
		else if (p[ind].f / k >= mid + 1) y.push_back(v[i]);
		else cur[p[ind].s / k].push_back(v[i]);
	}
 
	for (int j = 0; j < k; j++) {
		for (int x = 0; x < k; x++) {
			d[mid + 1][j][x] = 0;
		}
	}
	for (int i = mid; i >= l; i--) {
		for (int from = 0; from < k; from++) {
			for (int to = 0; to < k; to++) {
				d[i][from][to] = oo;
				for (int j = 0; j < k; j++) {
					
					if(i == mid) d[i][from][to] = dist[i][from][to];
					else d[i][from][to] = min(d[i][from][to], d[i + 1][j][to] + dist[i][from][j]);
				}
			
 			}
		}
	}
	for (int i = mid + 2; i <= r; i++) {
		for (int from = 0; from < k; from++) {
			for (int to = 0; to < k; to++) {
				d[i][from][to] = oo;
				for (int j = 0; j < k; j++) {
					if(i == mid+2) d[i][from][to] = dist[i-1][to][from];
					else d[i][from][to] = min(d[i][from][to], d[i - 1][j][to] + dist[i-1][j][from]);
				}
			}
		}
	}
	for (int i = mid + 1; i <= r; i++) {
		for (int j = 0; j < cur[i].size(); j++) {
			int ind = cur[i][j];
			ans[ind] = oo;
			for (int x = 0; x < k; x++) {
					ans[ind] = min(ans[ind], d[p[ind].f / k][p[ind].f % k][x]
 
						+ d[ind][p[i].s % k][x] );
			}
			if (i == mid + 1) ans[ind] = d[p[ind].f / k][p[ind].f % k][p[ind].s % k];
 
		}
	}
	solve(l, mid, x);
	solve(mid + 1, r, y);
}
signed main() {
	cin >> k >> n >> m >> q;
	for (int i = 0; i <= n / k; i++) {
		for (int j = 0; j < k; j++) {
			for (int x = 0; x < k; x++) dist[i][j][x] = oo;
		}
	}
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		dist[u / k][u % k][v % k] = w;
	}
	vector<int> all;
	for (int i = 1; i <= q; i++) {
		cin >> p[i].f >> p[i].s;
		ans[i] = oo;
		if (p[i].s <= p[i].f) ans[i] = -1;
		else all.push_back(i);
	}
	solve(0, n / k, all);
	for (int i = 1; i <= q; i++) {
		if (ans[i] == oo) cout << -1;
		else cout << ans[i];
		cout << "\n";
	}
 
}

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

toll.cpp: In function 'void solve(long long int, long long int, std::vector<long long int>)':
toll.cpp:16:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
toll.cpp:53:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for (int j = 0; j < cur[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~

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