(Div. 2, based on Olympiad of Metropolises)
题意：有n个地点,m次航班，每次航班有4个信息，起飞日期di、出发地fi、目的地ti、花费ci，起飞和出发地至少有一个是地点0。现在n个地点，每个地点有一个人，他们要到地点0，当所有人都到达的时候，一起待k天，然后再分别回到n个地点。问说最小的花费是多少，如果达不到这个要求输出-1。

参考博客：

http://blog.csdn.net/my_sunshine26/article/details/77876193

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#include<iostream>
using namespace std;
struct node
{
    int d,u,v,c;
} data[999999];
int cmp(node a,node b)
{
    return a.d<b.d;
}
long long vis[999999],ss[999999],tt[999999];
//第i天及以前能够全部到达0城市的最小花费ss[i],
//在第i天及以后能够全部离开0城市的最小花费tt[i]
int main()
{

    int n,m,k;
    cin>>n>>m>>k;
    int max_day=0;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d%d",&data[i].d,&data[i].u,&data[i].v,&data[i].c);
        max_day = max(max_day,data[i].d);
    }
    sort(data+1,data+1+m,cmp);
    int cnt = n;
    long long sum;
    memset(vis,0,sizeof(vis));
    for(int i=1; i<=m; i++)
    {
        if(data[i].u)//挑选出 u 0 的回家路线
        {
            int now  = data[i].d;
            if(!vis[data[i].u])
            {
                vis[data[i].u] = data[i].c;
                cnt--;
                if(cnt==0)
                {
                    sum =0 ;
                    for(int i=1; i<=n; i++)
                    {
                        sum+=vis[i];
                    }
                    ss[now] = sum;
                }
            }
            else if(vis[data[i].u]>data[i].c)
            {
                if(cnt==0)
                {



                      sum-= vis[data[i].u];
                    sum+=data[i].c;
                    vis[data[i].u] = data[i].c;
                    ss[data[i].d] = sum;

                }
                else
                    vis[data[i].u] = data[i].c;
            }
        }


    }
    if(cnt!=0)
    {
        puts("-1");
        return  0;
    }
    cnt = n;
    memset(vis,0,sizeof(vis));
    for(int i=m; i>=1; i--)
    {
        if(data[i].v)//挑选出 0 v 的回家路线
        {
            int now  = data[i].d;
            if(!vis[data[i].v])//假如当前还没有路线送这个人回去
            {
                vis[data[i].v] = data[i].c;
                cnt--;
              // cout<<data[i].v<<"&&&"<<endl;
                if(cnt==0)
                {
                    sum =0 ;
                    for(int i=1; i<=n; i++)
                    {
                        sum+=vis[i];
                    }
                    tt[now] = sum;
                }
            }
            else if(vis[data[i].v]>data[i].c)
            {
                if(cnt==0)
                {

                    sum-= vis[data[i].v];//此处非常重要，正是因为sum的继承，
                    //才会进行排序，从后往前扫描，使得最小值的更新有效
                    //此处会把所有 在路线中出现过的天数 算出符合要求的ss和tt结果
                    sum+=data[i].c;
                    vis[data[i].v] = data[i].c;
                    tt[data[i].d] = sum;

                }
                else
                    vis[data[i].v] = data[i].c;
            }
        }
    }


    if(cnt!=0)
    {
        puts("-1");
        return  0;
    }
// for(int i=1;i<=max_day;i++)
// {
// printf("%lld %lld\n",ss[i],tt[i]);
// }

// 顺序跑完之后再进行一边最小值的更新
//因为有可能这一天根本就没在路线中出现过
//但是这一天在符合要求的天数后边，确实还是符合要求，
//所以需要把这些天数给更新掉
    for(int i=1; i<=max_day; i++)
    {
        if(!ss[i]) ss[i] = ss[i-1];
        if(ss[i]&&ss[i-1])
            ss[i] = min(ss[i],ss[i-1]);
    }

    for(int i=max_day; i>=1; i--)
    {
        if(!tt[i])tt[i] = tt[i+1];
        if(tt[i]&&tt[i+1]) tt[i] = min(tt[i],tt[i+1]);

    }


    long long ans = 1e18;
    //最后一班送专家回家的飞机时间为数据中出现的最大时间
    for(int i=1; i<=max_day-k-1; i++)
    {
        if(ss[i]&&tt[i+k+1])//确保所有乘客都可以聚在一起且回去
            ans = min(ans,ss[i]+tt[i+k+1]);
    }
    if(ans!=1e18) cout<<ans<<endl;
    else puts("-1");


    return 0;
}