Submission #1311982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311982		xlpaun	Drivers (BOI24_drivers)	C++20	0 / 100	1 ms	572 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<vector<pair<int,int>>>adj;
vector<int>dist;
void dijsktra(int start, vector<vector<pair<int,int>>>& adj){
	dist.clear();
	dist.resize(adj.size(), 1e18);
	dist[start] = 0;
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>>pq;
	pq.push({0,start});
	
	
	while (!pq.empty()){
		
		int current_node_dist = pq.top().first;
		int current_node = pq.top().second;
		
		pq.pop();
		if (current_node_dist > dist[current_node]) continue;
		
		for(int i = 0; i < adj[current_node].size(); i++){
			
			int neighbour = adj[current_node][i].first;
			int dist_from_neighbour = adj[current_node][i].second;
			
			
			if (dist[neighbour] > dist[current_node] + dist_from_neighbour){
				dist[neighbour] = dist[current_node] + dist_from_neighbour;
				pq.push({dist[neighbour],neighbour});
			}
		}
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	int cities, roads, coms;
	cin >> cities >> roads >> coms;

	adj.resize(cities);
	for (int i = 0; i < roads; i++){
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		adj[a].push_back({b,c});
		adj[b].push_back({a,c});
	}
	for (int i = 0; i < coms; i++){
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		dijsktra(a, adj);
		if (dist[b] > c){
			cout << "NE";
		}else{
			cout << "TAIP";
		}
		cout << '\n';
	}
	
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 23
• Subtask 5: 0 / 45