CF853B

CF853B

​​ Country of Metropolia is holding Olympiad of Metrpolises soon. It mean that all jury members of the olympiad should meet together in Metropolis (the capital of the country) for the problem preparation process.

There are n + 1 cities consecutively numbered from 0 to n. City 0 is Metropolis that is the meeting point for all jury members. For each city from 1 to n there is exactly one jury member living there. Olympiad preparation is a long and demanding process that requires k days of work. For all of these k days each of the n jury members should be present in Metropolis to be able to work on problems.

You know the flight schedule in the country (jury members consider themselves important enough to only use flights for transportation). All flights in Metropolia are either going to Metropolis or out of Metropolis. There are no night flights in Metropolia, or in the other words, plane always takes off at the same day it arrives. On his arrival day and departure day jury member is not able to discuss the olympiad. All flights in Megapolia depart and arrive at the same day.

Gather everybody for k days in the capital is a hard objective, doing that while spending the minimum possible money is even harder. Nevertheless, your task is to arrange the cheapest way to bring all of the jury members to Metrpolis, so that they can work together for kdays and then send them back to their home cities. Cost of the arrangement is defined as a total cost of tickets for all used flights. It is allowed for jury member to stay in Metropolis for more than k days.

Input The first line of input contains three integers n, m and k (1 ≤ n ≤ 105, 0 ≤ m ≤ 105, 1 ≤ k ≤ 106).

The i-th of the following m lines contains the description of the i-th flight defined by four integers di, fi, ti and ci (1 ≤ di ≤ 106,0 ≤ fi ≤ n, 0 ≤ ti ≤ n, 1 ≤ ci ≤ 106, exactly one of fi and ti equals zero), the day of departure (and arrival), the departure city, the arrival city and the ticket cost.

Output Output the only integer that is the minimum cost of gathering all jury members in city 0 for k days and then sending them back to their home cities.

If it is impossible to gather everybody in Metropolis for k days and then send them back to their home cities, output “-1” (without the quotes).

Examples input 2 6 5 1 1 0 5000 3 2 0 5500 2 2 0 6000 15 0 2 9000 9 0 1 7000 8 0 2 6500 output 24500 input 2 4 5 1 2 0 5000 2 1 0 4500 2 1 0 3000 8 0 1 6000 output -1 Note The optimal way to gather everybody in Metropolis in the first sample test is to use flights that take place on days 1, 2, 8 and 9. The only alternative option is to send jury member from second city back home on day 15, that would cost 2500 more.

In the second sample it is impossible to send jury member from city 2 back home from Metropolis.

首先先大致阐述下题意：n个城市都要到城市0(首都)开会，开会时长为k天，而且掐头去尾k天 可以停留超过k天

我们要选择总机票花费最小来做

我们预处理两个数组dp[i]&dp1[i]分别表示

dp[i]表示截止到第i天所有代表已经抵达首都的最小花费

dp1[i]表示从第i天开始陆续有代表离开，并且一定在最后一天前所有代表都离开了的最小花费

#include#include#include#define N 1100000#define inf 1LL<<60using namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch<='9'&&ch>='0') {x=x*10+ch-'0';ch=getchar();} return x*f;}struct node{ int t,de,te,c;}data[N];inline bool cmp(node a,node b){ return a.t=t-1) {printf("-1");return 0;} for (int i=s+1;i<=t-2;++i) dp[i]=min(dp[i],dp[i-1]); for (int i=1;i<=t;++i) dp1[i]=inf; tot=sum=0;memset(min1,0,sizeof(min1)); for (int i=m;i>=1;--i){ if (data[i].te==0) continue; int te=data[i].te,cost=data[i].c; if (min1[te]==0) min1[te]=cost,tot++,sum+=cost;else if (cost0&&dp[s]==inf)--s; if (s<1){printf("-1");return 0;} for (int i=s-1;i>=1;--i) dp1[i]=min(dp1[i],dp1[i+1]);// for (int i=1;i<=t;++i) printf("%d,dp[i]);printf("\n");// for (int i=1;i<=t;++i) printf("%d,dp1[i]);printf("\n"); ans=inf; for (int i=1;i+k+1<=t;++i){ if (dp[i]==inf||dp1[i+k+1]==inf) continue; ans=min(ans,dp[i]+dp1[i+k+1]); } if (ans==inf) printf("-1");else printf("%lld",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。