제출 #701670

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
701670		delrey	Autobus (COCI22_autobus)	C++14	15 / 70	1081 ms	588 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int inf = 1000000000;
int n, m, k, qn;
int adj[70][70];
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 < n; i++)
        for(int j = 0; j < n; j++)
            adj[i][j] = inf;
    for(int i = 0; i < m; i++)
    {
        int a, b, t;
        cin>>a>>b>>t;
        a--;
        b--;
        adj[a][b] = min(adj[a][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;
            if(dis == k)
                continue;
            for(int i = 0; i < n; i++)
                if(t[a] + adj[a][i] < t[i])
                    q.push({{-(d[a] + 1), -(t[a] + adj[a][i])}, i});
        }
        /*
        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: 15 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 15