Submission #1312038

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

Main

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

const string yes = "TAIP";
const string no = "NE";

int32_t main() {
    int n, e, q;cin>>n>>e>>q;
    vector<pair<int, int>> M[n];
        for (int i = 0; i < e; i++) {
            int a, b, k;cin>>a>>b>>k;a--,b--;
            M[a].push_back(make_pair(b, k));
            M[b].push_back(make_pair(a, k));
        }
    vector<string> ANS;
    
    for (int i = 0; i < q; i++) {
        int a, b, k;cin>>a>>b>>k;a--,b--;
        vector<int> D(n, LLONG_MAX);D[a]=0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> PQ;PQ.emplace(0,a);
        while (!PQ.empty()) {
            pair<int, int> top = PQ.top();PQ.pop();
            if (top.first > D[top.second])
                continue;
            
            for (pair<int, int> &p: M[top.second]) {
                if (D[top.second] + p.second < D[p.first]) {
                    D[p.first] = D[top.second] + p.second;   
                    PQ.emplace(D[p.first], p.first);
                }
            }
        }
        ANS.push_back((D[b] <= k)? yes: no);
    }
    for (string &s: ANS)
        cout << s << '\n';
    return 0;
}

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