Submission #994894

#	Time	Username	Problem	Language	Result	Execution time	Memory
994894		Aiperiii	Toll (BOI17_toll)	C++14	100 / 100	2418 ms	9696 KiB

toll

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,k,m,q;
    cin>>k>>n>>m>>q;
    vector <pair <int,int> > g[n];
    while(m--){
        int u,v,x;
        cin>>u>>v>>x;
        g[u].pb({v,x});
    }
    while(q--){
        int u,v;
        cin>>u>>v;
        vector <int> dp(n,1e18);
        dp[u]=0;
        for(int i=u;i<v;i++){
            for(auto x : g[i]){
                dp[x.ff]=min(dp[x.ff],dp[i]+x.ss);
            }
        }
        if(dp[v]==1e18)dp[v]=-1;
        cout<<dp[v]<<"\n";
    }
}
/*
 5 14 5 5
 0 5 9
 5 12 10
 0 7 7
 7 12 8
 4 7 10
 0 12
 0 5
 0 7
 7 12
 0 13
*/

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