Submission #1183690

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

toll

#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<long long,long long>>> vec;
vector<vector<long>> dis;
vector<bool> vis;
long long raiz;
void bfs(int nodo)
{
    priority_queue<pair<long long,long long>> 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<long long,long long> 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()
{
    long long k,n,m,o; cin>>k>>n>>m>>o;
    vec.assign(n,vector<pair<long long,long long>> ());
    vis.assign(n,false);
    dis.assign(n,vector<long> (n,1e6+1));
    long long 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--){
    cin>>p>>g; 
    if(dis[p][p]!=0) {vis.assign(n,false); bfs(p);}
    if(dis[p][g]==1e6+1) cout<<"-1"<<endl;
    else cout<<dis[p][g]<<endl;
    } 
    // for(auto x:dis)
    // {
    //     for(auto y:x)
    //     cout<<y<<" ";
    //     cout<<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