Submission #164056

#	Time	Username	Problem	Language	Result	Execution time	Memory
164056		nvmdava	Toll (BOI17_toll)	C++17	49 / 100	3026 ms	8412 KiB

toll

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 50005
#define INF 0x3f3f3f3f
#define MOD 1000000007LL

vector<pair<int, int> > adj[N], q[N];
int dis[N], mx[N];
vector<int> tmp;
int ans[N];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    memset(dis, 0x3f, sizeof dis);

    int k, n, m, o;
    cin>>k>>n>>m>>o;
    while(m--){
    	int a, b, t;
    	cin>>a>>b>>t;
    	adj[a].push_back({b, t});
    }
    for(int i = 1; i <= o; ++i){
    	int s, e;
    	cin>>s>>e;
    	mx[s] = max(mx[s], e);
	    q[s].push_back({e, i});
    }

    for(int i = 0; i < n; ++i){
    	if(mx[i] < i)
    		continue;
    	dis[i] = 0;
    	for(int j = i; j < mx[i]; ++j){
    		if(dis[j] == INF)continue;
    		for(auto& x : adj[j])
    			if(x.ff <= mx[i]) 
 		   			dis[x.ff] = min(dis[j] + x.ss, dis[x.ff]);
    		
    	}
    	for(auto& x : q[i])
    		ans[x.ss] = (dis[x.ff] == INF ? -1 : dis[x.ff]);
    	for(int j = i; j <= mx[i]; ++j)
    		dis[j] = INF;
    	
    }

    for(int i = 1; i <= o; ++i)
    	cout<<ans[i]<<'\n';
}

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