代码

#include <bits/stdc++.h>
#define ll long long
#define M 4005
#define getchar nc
using namespace std;
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    register int x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*f;
}
inline void write(register ll x)
{
    if(!x)putchar('0');if(x<0)x=-x,putchar('-');
    static int sta[20];register int tot=0;
    while(x)sta[tot++]=x%10,x/=10;
    while(tot)putchar(sta[--tot]+48);
}
inline ll Min(register ll a,register ll b)
{
    return a<b?a:b;
}
int n,m,A,B,C;
struct edge{
    int u,v,p,q;
}e[M];
namespace solve1{
    vector< pair<int,ll> > v[M*M];
    struct node{
        ll dis;
        int pos;
        bool operator <( const node &x )const
        {
            return x.dis < dis;
        }
    };
    std::priority_queue<node>q;
    ll dis[M*M];
    bool vis[M*M];
    inline void dijkstra()
    {
        dis[m*(m+1)+1]=0;
        q.push((node){0,m*(m+1)+1});
        while(!q.empty())
        {
            node tmp=q.top();
            q.pop();
            int x=tmp.pos;
            if(vis[x])
                continue;
            vis[x]=1;
            for(register int i=0;i<v[x].size();++i)
            {
                int y=v[x][i].first;
                if(dis[y]>dis[x]+v[x][i].second)
                {
                    dis[y]=dis[x]+v[x][i].second;
                    if(!vis[y])
                        q.push((node){dis[y],y});
                }
            }
        }
    }
    inline void solve()
    {
        for(register int i=1;i<=m;++i)
        {
            for(register int j=1;j<=m;++j)
            {
                if(i==j)
                    continue;
                if(e[i].v!=e[j].u||e[i].q>e[j].p)
                    continue;
                if(e[i].v!=n)
                {
                    v[1+(i-1)*(m+1)].push_back(make_pair((i-1)*(m+1)+j+1,e[i].q-e[i].p));
                    v[(i-1)*(m+1)+j+1].push_back(make_pair(1+(j-1)*(m+1),1ll*A*(e[j].p-e[i].q)*(e[j].p-e[i].q)+B*(e[j].p-e[i].q)+(e[j].p-e[i].q)+C));
                    //printf("%d %d %lld\n",1+(i-1)*(m+1),(i-1)*(m+1)+j+1,e[i].q-e[i].p);
                    //printf("%d %d %lld\n",(i-1)*(m+1)+j+1,1+(j-1)*(m+1),1ll*A*(e[j].p-e[i].q)*(e[j].p-e[i].q)+B*(e[j].p-e[i].q)+(e[j].p-e[i].q)+C);
                }
            }
            if(e[i].v==n)
            {
                v[1+(i-1)*(m+1)].push_back(make_pair(m*(m+1)+2,e[i].q-e[i].p));
                //printf("%d %d %lld\n",1+(i-1)*(m+1),m*(m+1)+2,e[i].q-e[i].p);
            }
            if(e[i].u==1)
            {
                v[m*(m+1)+1].push_back(make_pair(1+(i-1)*(m+1),1ll*A*e[i].p*e[i].p+B*e[i].p+e[i].p+C));
                //printf("%d %d %lld\n",m*(m+1)+1,1+(i-1)*(m+1),e[i].p);
            }
        }
        for(register int i=1;i<=m*(m+1)+2;++i)
            dis[i]=1145141919810ll;
        dijkstra();
        write(dis[m*(m+1)+2]),puts("");
        //for(register int i=1;i<=m*(m+1)+2;++i)
        //    write(dis[i]),puts("");
    }
}
// namespace solve2{
//     vector <int> t[N];
//     vector< pair<int,ll> > v[N*5];
//     map<int,int> ma;
//     int qwqwq;
//     struct node{
//         ll dis;
//         int pos;
//         bool operator <( const node &x )const
//         {
//             return x.dis < dis;
//         }
//     };
//     std::priority_queue<node>q;
//     int len[N];
//     ll dis[N*5];
//     bool vis[N*5];
//     inline void dij()
//     {
//         dis[1]=0;
//         q.push((node){0,1});
//         while(!q.empty())
//         {
//             node tmp=q.top();
//             q.pop();
//             int x=tmp.pos;
//             if(vis[x])
//                 continue;
//             vis[x]=1;
//             for(register int i=0;i<v[x].size();++i)
//             {
//                 int y=v[x][i].first;
//                 if(dis[y]>dis[x]+v[x][i].second)
//                 {
//                     dis[y]=dis[x]+v[x][i].second;
//                     if(!vis[y])
//                         q.push((node){dis[y],y});
//                 }
//             }
//         }
//     }
//     inline void ssolve()
//     {
//         t[1].push_back(0);
//         for(register int i=1;i<=m;++i)
//             t[e[i].u].push_back(e[i].p),t[e[i].v].push_back(e[i].q);
//         for(register int i=1;i<=n;++i)
//         {
//             sort(t[i].begin(),t[i].end());
//             len[i]=unique(t[i].begin(),t[i].end())-t[i].begin();
//         }
//         for(register int i=1;i<=n;++i)
//         {
//             for(register int j=1;j<len[i];++j)
//             {
//                 int t1=t[i][j-1],t2=t[i][j];
//                 int xxx=(i-1)*1001+t1,yyy=(i-1)*1001+t2;
//                 if(j==1)
//                     ma[xxx]=++qwqwq;
//                 ma[yyy]=++qwqwq;
//                 v[ma[xxx]].push_back(make_pair(ma[yyy],1ll*B*(t2-t1)+C));
//                 printf("%d %d %d %d\n",xxx,yyy,ma[xxx],ma[yyy]);
//             }
//             if(len[i]==1)
//                 ma[(i-1)*1001+t[i][0]]=++qwqwq;
//         }
//         for(register int i=1;i<=m;++i)
//         {
//             v[ma[(e[i].u-1)*1001+e[i].p]].push_back(make_pair(ma[(e[i].v-1)*1001+e[i].q],0));
//             printf("%d %d %d %d\n",(e[i].u-1)*1001+e[i].p,(e[i].v-1)*1001+e[i].q,ma[(e[i].u-1)*1001+e[i].p],ma[(e[i].v-1)*1001+e[i].q]);
//         }
//         for(register int i=1;i<=qwqwq;++i)
//             dis[i]=1145141919810ll;
//         dij();
//         ll ans=1145141919810ll;
//         for(register int i=0;i<len[n];++i)
//             ans=Min(ans,dis[ma[(n-1)*1001+t[n][i]]]+t[n][i]);
//         write(ans),puts("");
//     }
// }
int main()
{
    freopen("route.in","r",stdin);
    freopen("route.out","w",stdout);
    n=read(),m=read(),A=read(),B=read(),C=read();
    for(register int i=1;i<=m;++i)
    {
        int u=read(),v=read(),p=read(),q=read();
        e[i]=(edge){u,v,p,q};
    }
    //puts("233");
	// if(A!=0)
		solve1::solve();
    // else
    //     solve2::ssolve();
	return 0;
}

评测结果