Submission #864551

#	Time	Username	Problem	Language	Result	Execution time	Memory
864551		iskhakkutbilim	Toll (BOI17_toll)	C++17	56 / 100	3051 ms	9096 KiB

toll

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 5e4;
const int mod = 1e17;
vector< pair<int, int> > g[N];
int k, n, m, q;
main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	cin >> k >> n >> m >> q;
	vector<int> dis(n, mod), parent(n, -1);
	for(int i = 0;i < m; i++){
		int a, b, w; cin >> a >> b >> w;
		
		g[a].push_back({b, w});
	}
	
	vector<pair<int, int> > Q;
	int z = 0;
	for(int i = 0;i < q; i++){
		int a, b; cin >> a >> b;
		z+= (a == 0);
		Q.push_back({a, b});
	}
	dis[0] = 0;
	for(int i = 0; i < n; i++){
		for(auto [to, w] : g[i]){
			if(dis[to] > dis[i] + w){
				dis[to] = dis[i] + w;
				parent[to] = i;
			}
		}
	}
	if(z == q){
		for(auto [a, b] : Q){
			if(a == b){
				cout << 0 << '\n';
				continue;
			}
			if(dis[b] >= mod) cout << "-1" << '\n';
			else cout << dis[b]<< '\n';
		}
		
		
		return 0;
	}
	
	for(auto [a, b] : Q){
		if(a == b){
			cout << 0 << '\n';
			continue;
		}
		for(int i = 0;i < n; i++) dis[i] = mod;
		dis[a] = 0;
		for(int i = a; i < n; i++){
			for(auto [to, w] : g[i]){
				if(dis[to] > dis[i] + w){
					dis[to] = dis[i] + w;
				}
			}
		}
		if(dis[b] >= mod) cout << "-1\n";
		else cout << dis[b] << '\n';
	}
	return 0;
}
 

Compilation message (stderr)

toll.cpp:12:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   12 | main(){
      | ^~~~

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