oj.uz

Submission #737734

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

int bfs(int raiz, int b, vector<vector<pair<int,int>>>&listaAdy){
    vector<int>sol(listaAdy.size());
    sol[raiz]=0;
    queue<int>colaBFS;
    vector<bool>visitado(listaAdy.size(), false);
    colaBFS.push(raiz);
    visitado[raiz]=true;
    int nodoActual;
    while(!colaBFS.empty()) {
        nodoActual=colaBFS.front();
        if (nodoActual==b) return sol[nodoActual];
        colaBFS.pop();
        for (pair<int,int> conexion: listaAdy[nodoActual]) {
            if (!visitado[conexion.first]) {
                colaBFS.push(conexion.first);
                visitado[conexion.first]=true;
                sol[conexion.first]=sol[nodoActual]+1;
            }
        }
    }return -1;
}

long long int Dijkstra(int a, int b, vector<vector<pair<int, int>>>&listaAdy, int k) {
    int N=(int)listaAdy.size();
    vector<long long int>distancia(N, 1e18);
    vector<int>usado(N, 0);
    distancia[a]=0;
    priority_queue<pair<long long int, int>>pq;
    pq.push(make_pair(0, a));
    while(!pq.empty()) {
        int nodo=pq.top().second;
        long long int distanciaAlt=-pq.top().first;
        pq.pop();
        if (distanciaAlt>distancia[nodo]) continue;
        if (usado[nodo]==k and nodo!=b){
            int x=bfs(nodo, b, listaAdy);
            if (x!=-1){
                distancia[nodo]=Dijkstra(a, nodo, listaAdy, k-x);
                usado[nodo]=k-x;
            }continue;
        }for (pair<int, int> vecino: listaAdy[nodo]) {
            int nodoVecino=vecino.first;
            long long int costeVecino=vecino.second;
            if (distancia[nodoVecino]>distancia[nodo]+costeVecino) {
                distancia[nodoVecino]=distancia[nodo]+costeVecino;
                pq.push(make_pair(-distancia[nodoVecino], nodoVecino));
                usado[nodoVecino]=usado[nodo]+1;
            }
        }
    }return distancia[b];
}

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;
        long long int res=Dijkstra(a-1, b-1, listaAdy, k);
        if (res==1000000000000000000) cout<<-1<<endl;
        else cout<<res<<endl;
    }return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 352 KB Output is correct
2 Execution timed out 1063 ms 364 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 60 ms 332 KB Output is correct
8 Correct 58 ms 364 KB Output is correct
9 Execution timed out 1078 ms 352 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 315 ms 352 KB Output is correct
8 Execution timed out 1063 ms 364 KB Time limit exceeded
9 Halted 0 ms 0 KB -