oj.uz

Submission #737754

# Submission time Handle Problem Language Result Execution time Memory
737754 2023-05-07T16:59:05 Z lalig777 Autobus (COCI22_autobus) C++14
0 / 70
 1000 ms 455100 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

void bfs(int a, int b, vector<vector<pair<int,int>>>&listaAdy, int k){
    vector<int>calles(listaAdy.size());
    calles[a]=0;
    vector<long long int>distancia(listaAdy.size(), 1e18);
    distancia[a]=0;
    queue<int>colaBFS;
    colaBFS.push(a);
    int nodoActual;
    while(!colaBFS.empty()) {
        nodoActual=colaBFS.front();
        if (calles[nodoActual]==k) break;
        colaBFS.pop();
        for (pair<int,int> conexion: listaAdy[nodoActual]) {
            colaBFS.push(conexion.first);
            calles[conexion.first]=calles[nodoActual]+1;
            distancia[conexion.first]=min(distancia[conexion.first], distancia[nodoActual]+conexion.second);
        }
    }if (distancia[b]==1000000000000000000) cout<<-1<<endl;
    else cout<<distancia[b]<<endl;
}


int main(){
    int n, m, a, b, t, k, q;
    cin>>n>>m;
    vector<vector<pair<int, int>>>listaAdy(n);
    for (int i=0; i<m; i++){
        cin>>a>>b>>t;
        listaAdy[a-1].push_back(make_pair(b-1, t));
    }cin>>k>>q;
    for (int i=0; i<q; i++){
        cin>>a>>b;
        bfs(a-1, b-1, listaAdy, k);
    }return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 173728 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 455100 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 173728 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 173728 KB Time limit exceeded
2 Halted 0 ms 0 KB -