제출 #1283153

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283153		abc123	Drivers (BOI24_drivers)	C++20	11 / 100	2094 ms	1140 KiB

Main

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// Each road is an edge: to, time
struct Road {
    int to, time;
};

int main() {
    int N, M, U;
    cin >> N >> M >> U;

    vector<vector<Road>> graph(N + 1);

    // Reading roads
    for (int i = 0; i < M; ++i) {
        int x, y, t;
        cin >> x >> y >> t;
        graph[x].push_back({y, t});
        graph[y].push_back({x, t}); // Undirected
    }

    // Answer each query
    for (int i = 0; i < U; ++i) {
        int a, b, p;
        cin >> a >> b >> p;

        // BFS from a, only use roads with time <= p
        vector<bool> visited(N + 1, false);
        queue<int> q;
        visited[a] = true;
        q.push(a);
        bool found = false;

        while (!q.empty()) {
            int city = q.front(); q.pop();
            if (city == b) {
                found = true;
                break;
            }
            for (auto &road : graph[city]) {
                if (road.time <= p && !visited[road.to]) {
                    visited[road.to] = true;
                    q.push(road.to);
                }
            }
        }
        if (found) cout << "TAIP\n";
        else cout << "NE\n";
    }
    return 0;
}

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