oj.uz

Submission #701668

# Submission time Handle Problem Language Result Execution time Memory
701668 2023-02-21T21:04:33 Z delrey Autobus (COCI22_autobus) C++14
0 / 70
 218 ms 480 KB 
#include <bits/stdc++.h>

using namespace std;

const int inf = 1000000000;
int n, m, k, qn;
vector <pair<int, int> > v[70]; //{{town A, town B}, time}
int d[70], t[70];
priority_queue <pair<pair<int, int>, int> > q; //{{distance, time}, town}

int main()
{
    cin>>n>>m;
    for(int i = 0; i < m; i++)
    {
        int a, b, t;
        cin>>a>>b>>t;
        a--;
        b--;
        v[a].push_back({b, t});
    }
    cin>>k>>qn;
    while(qn--)
    {
        int from, to;
        cin>>from>>to;
        from--;
        to--;
        for(int i = 0; i < n; i++)
            d[i] = t[i] = inf;
        q.push({{0, 0}, from});
        while(q.size())
        {
            int dis = -q.top().first.first;
            int tim = -q.top().first.second;
            int a = q.top().second;
            q.pop();
            if(dis > k || t[a] <= tim)
                continue;
            d[a] = dis;
            t[a] = tim;
            for(size_t i = 0; i < v[a].size(); i++)
                if(d[a] == k || t[a] + v[a][i].second < d[v[a][i].first])
                    q.push({{-(d[a] + 1), -(t[a] + v[a][i].second)}, v[a][i].first});
        }
        /*
        cout<<"d: ";
        for(int i = 0; i < n; i++)
            cout<<d[i]<<" ";
        cout<<endl<<"t: ";
        for(int i = 0; i < n; i++)
            cout<<t[i]<<" ";
        cout<<endl<<"r: ";*/
        if(t[to] == inf)
            cout<<-1<<endl;
        else
            cout<<t[to]<<endl;
    }
    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 368 KB Output is correct
2 Correct 109 ms 348 KB Output is correct
3 Incorrect 218 ms 480 KB Output isn't correct
4 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 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 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 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -