代码

#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;
    cin>>n>>m>>A>>B>>C;
    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,(long long)sum[q[i].from][j]+(long long)A*y*y+(long long)B*y+C);
        }
        if (minn!=(long long)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]);
    cout<<ans<<endl;
    return 0;
}

评测结果