Submission #701668

#	Time	Username	Problem	Language	Result	Execution time	Memory
701668		delrey	Autobus (COCI22_autobus)	C++14	0 / 70	218 ms	480 KiB

Main

#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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 15