Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define readFile freopen("input","r",stdin)
- #define writeFile freopen("output","w",stdout)
- #define fastIO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
- typedef unsigned long long ull;
- typedef long long LL;
- typedef pair<long long,long long> ii;
- const double eps = 1e-10;
- const long long mod = 1e9+7;
- const long long INF = 1e17;
- const int N = 100001,M = 51;
- vector<vector<pair<ii,int> > > G;
- long long n,m,a,b,c,d;
- ii dp[N];
- int main() {
- #ifndef ONLINE_JUDGE
- readFile;
- // writeFile;
- #endif
- G.resize(N);
- cin>>n>>m;
- for(int i=1;i<=n;i++){
- cin>>a>>b>>c>>d;
- G[a].push_back(make_pair(make_pair(c,d),b));
- }
- for(int i=1;i<N;i++) dp[i] = make_pair(INF,INF);
- dp[0] = make_pair(0,0);
- for(int i=1;i<=m;i++){
- if (dp[i-1]==make_pair(INF,INF)) continue;
- for(int j=0;j<G[i].size();j++){
- int u = G[i][j].second;
- if (dp[u].first>max(dp[i-1].first,G[i][j].first.first)){
- dp[u] = make_pair(max(dp[i-1].first,G[i][j].first.first),dp[i-1].second+G[i][j].first.second);
- }
- else if (dp[u].first==max(dp[i-1].first , G[i][j].first.first)){
- dp[u].second = min(dp[u].second,dp[i-1].second+G[i][j].first.second);
- }
- }
- }
- cout<<dp[m].first<<" "<<dp[m].second;
- }
Advertisement
Add Comment
Please, Sign In to add comment