Submission #1176344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176344		minhpk	Toll (BOI17_toll)	C++20	0 / 100	3096 ms	28660 KiB

toll

#include <bits/stdc++.h>
#define int long long
using namespace std;
int k,a,b,c;
vector <pair<int,int>> z[1000005];

int cnt[100005];
int bruh=1e18;
void dijkstra(int sta,int fin){
    for (int i=sta;i<=fin;i++){
         cnt[i]=bruh;
    }
    priority_queue<pair<int,int> , vector <pair<int,int>> , greater<pair<int,int>> > q;
    q.push({0,sta});
    cnt[sta]=0;
    while (q.size()){
         pair<int,int> pos=q.top();
         q.pop();
         int pos1=pos.second;
         int val=pos.first;
         if (val>cnt[pos1]){
            continue;
         }
         if (pos1/5>fin/5){
            continue;
         }
         for (auto p:z[pos1]){
              if (cnt[p.first]>p.second+val){
                  cnt[p.first]=p.second+val;
                  q.push({cnt[p.first],p.first});
              }
         }
    }
    if (cnt[fin]!=bruh){
        cout << cnt[fin] << "\n";
    }else{
        cout << -1 << "\n";
    }


}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> k >> a >> b >> c;
    for (int i=1;i<=b;i++){
        int x,y,t;
        cin>>  x >> y >> t;
        z[x].push_back({y,t});
        z[y].push_back({x,t});
    }
    for (int i=1;i<=c;i++){
         int x,y;
         cin >> x >> y;
         dijkstra(x,y);
    }
    return 0;
}

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