Submission #1306198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306198		Robert_junior	Toll (BOI17_toll)	C++20	100 / 100	2075 ms	6424 KiB

toll

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define all(x) x.begin(), x.end()
#define ins insert
#define pb push_back
#define F first
#define S second
#define bt bitset<5010>
const int N = 1e5 + 100, K = 1610;
const int mod = 998244353;
int n, m, k, q;
vector<pair<int, int>>g[N];
int dp[N];
void solve(){
    cin>>k>>n>>m>>q;
    for(int i = 1; i <= m; i++){
        int u, v, w;
        cin>>u>>v>>w;
        g[u].pb({v, w});
    }
    while(q--){
        int a, b;
        cin>>a>>b;
        for(int i = a; i <= b; i++){
            dp[i] = INT_MAX;
        }
        dp[a] = 0;
        for(int i = a; i <= b; i++){
            for(auto [to, w] : g[i]){
                dp[to] = min(dp[to], dp[i] + w);
            }
        }
        cout<<(dp[b] == INT_MAX ? -1 : dp[b])<<'\n';
    }
}
main(){
	ios_base :: sync_with_stdio(false); 
	cin.tie(nullptr);
	int t = 1;
	//cin>>t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

toll.cpp:38:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   38 | main(){
      | ^~~~

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