Submission #628783

#	Time	Username	Problem	Language	Result	Execution time	Memory
628783		a_aguilo	Toll (BOI17_toll)	C++14	0 / 100	177 ms	4092 KiB

toll

#include<bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> v2pii;

int main(){
    int K, N, M, O, a, b, t;
    cin >> K >> N >> M >> O;
    v2pii listaAdy(N);
    for(int i = 0; i < M; ++i){
        cin >> a >> b >> t;
        listaAdy[a].push_back({b, t});
    }
    vi dist(N, -1);
    dist[0] = -1;
    pii inicio = {-0, 0};
    priority_queue<pii> PQ;
    PQ.push(inicio);
    while(!PQ.empty()){
        pii act = PQ.top(); PQ.pop();
        int distAct = -1*act.first;
        int nodo = act.second;
        cout << nodo << " " << distAct << endl;
        if( dist[nodo]!= -1) continue;
        dist[nodo] = distAct;
        for(pii vecino: listaAdy[nodo]){
            PQ.push({-1*(distAct+vecino.second), vecino.first});
        }
    }
    while(O--){
        cin >> a >> b;
        cout << dist[b] << endl;
    }
    return 0;
}

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