NOI2019D1T1

k1saki · 2019-07-17 18:54:26 · 题解

刚学提高组不久的蒟蒻被逼着打了同步赛，发现T1竟然A了

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int from;
    int to;
    int from_time;
    int to_time;
    node()
    {
    }
    node(int _a,int _b,int _c,int _d)
    {
        from=_a,to=_b,from_time=_c,to_time=_d;
    }
}q[200005];
bool cmp(node x,node y)
{
    if (x.from_time==y.from_time) return x.to_time<y.to_time;
    return x.from_time<y.from_time;
}
int read()
{
    int x=0;
    bool f=0;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')f=1;
        c=getchar();
    }
    while(isdigit(c))
    {
        x=x*10+c-'0';
        c=getchar();
    }
    if(f)x=-x;
    return x;
}
long long n,m,A,B,C,vis[100005][55],sum[100005][55],cnt[100005];
long long ans=1e18;
int main() {
    //freopen("route.in","r",stdin);
    //freopen("route.out","w",stdout);
    memset(vis,0x7fffffffffffffff,sizeof(vis));
    memset(sum,0x7fffffffffffffff,sizeof(sum));
    vis[1][1]=0;
    sum[1][1]=0;
    cnt[1]=1;//初始化 
    n=read(),m=read(),A=read(),B=read(),C=read();
    for (int i=0;i<m;i++)
    {
        int a=read(),b=read(),c=read(),d=read();
        q[i]=node(a,b,c,d);
    }
    sort(q,q+m,cmp);//按到达时间升序排序 
    for (int i=0;i<m;i++)
    {
        long long minn=0x7fffffffffffffff;
        for (int j=1;j<=cnt[q[i].from];j++)
        {
            if (vis[q[i].from][j]>q[i].from_time) continue;//如果上一班车到站时间已经晚于这班出发时间，就不用继续循环了 
            int y=q[i].from_time-vis[q[i].from][j];
            minn=min(minn,sum[q[i].from][j]+A*y*y+B*y+C);
        }
        if (minn!=0x7fffffffffffffff)
        {
            sum[q[i].to][++cnt[q[i].to]]=minn;
            vis[q[i].to][cnt[q[i].to]]=q[i].to_time;
        }
    }
    for (int i=1;i<=cnt[n];i++)ans=min(ans,sum[n][i]+vis[n][i]);
    printf("%lld\n",ans);
    return 0;
}

最慢的点218ms（还是数据太水才过的）