| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1311974 | xlpaun | Drivers (BOI24_drivers) | C++20 | 0 ms | 0 KiB |
#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(), 1e9+5);
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;
p
q.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';
}
}
