Submission #1182998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182998		gabyferaq	Toll (BOI17_toll)	C++20	0 / 100	248 ms	3380 KiB

toll

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<vector<pair<int,int>>> vec;
vector<int> dis;
vector<bool> vis;
void bfs(int nodo)
{
    priority_queue<pair<int,int>> cola;
    cola.push({0,nodo});
    dis[nodo]=0;
    while(!cola.empty())
    {
        nodo=cola.top().second;
        cola.pop();
        if(!vis[nodo]){
            for(pair<int,int> next:vec[nodo]) {
                if(dis[nodo]+next.second<dis[next.first]){
                    dis[next.first]=dis[nodo]+next.second;
                    cola.push({-dis[next.first],next.first});
                }
            }
            vis[nodo]=true;
        }
    }
}
void solve()
{
    ll k,n,m,o; cin>>k>>n>>m>>o;
    vec.assign(n,vector<pair<int,int>> ());
    ll a,b,t;
    while(m--)
    {
        cin>>a>>b>>t;
        if(b==a+1)
        vec[a].push_back({b,t});
    }
    while(o--){
    vis.assign(n,false);
    dis.assign(n,1e6+1);
    cin>>a>>b;
    bfs(a); 
    if(dis[b]==1e6+1) cout<<"-1"<<endl;
    else cout<<dis[b]<<endl;
    }
}
int main()
{
    solve();
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44