Submission #1183650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183650		gabyferaq	Toll (BOI17_toll)	C++20	8 / 100	3095 ms	6612 KiB

toll

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

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