Submission #1183663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183663		gabyferaq	Toll (BOI17_toll)	C++20	0 / 100	262 ms	589824 KiB

toll

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

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