代码

#include <bits/stdc++.h>
using namespace std;
const int MAXM=4040,INF=0x3f3f3f3f;
inline int read(){
	int x=0,f=1;char c=getchar();
	while (!isdigit(c)){if (c=='-') f=-1;c=getchar();}
	while (isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
	return x*f;
}
struct Edge{
	int from,to,dist;
	Edge(int u,int v,int d):from(u),to(v),dist(d){}
};
struct HeapNode{
	int d,u;
	bool operator <(const HeapNode& rhs)const{
		return d>rhs.d;
	}
};
struct Dijkstra{
	int n,m;
	vector<Edge> edges;
	vector<int> G[MAXM];
	int d[MAXM];	
	void init(int n){
		this->n=n;
		for (int i=0;i<=n;i++) G[i].clear();
		edges.clear();
	}
	void AddEdge(int from,int to,int dist){
		edges.push_back(Edge(from,to,dist));
		m=edges.size();
		G[from].push_back(m-1);
	}
	void dijkstra(int s){
		priority_queue<HeapNode> Q;
		for (int i=0;i<=n;i++) d[i]=INF;
		d[s]=0;Q.push((HeapNode){0,s});
		while (!Q.empty()){
			HeapNode x=Q.top();Q.pop();
			int u=x.u;
			if (x.d!=d[u]) continue;
			for (int i=0;i<G[u].size();i++){
				Edge& e=edges[G[u][i]];
				if (d[e.to]>d[u]+e.dist){
					d[e.to]=d[u]+e.dist;
					Q.push((HeapNode){d[e.to],e.to});
				}
			}
		}
	}
}Dij;
int n,m,A,B,C,S,T;
struct node{
	int u,v,l,r;
}a[MAXM];
int main(){
	freopen("route.in","r",stdin);freopen("route.out","w",stdout);
	n=read(),m=read(),A=read(),B=read(),C=read();
	for (int i=1;i<=m;i++) a[i].u=read(),a[i].v=read(),a[i].l=read(),a[i].r=read();
	Dij.init(m+1);S=0,T=m+1;
	for (int i=1;i<=m;i++)
		for (int j=1;j<=m;j++){
			if (i!=j&&a[i].v==a[j].u&&a[j].l>=a[i].r)Dij.AddEdge(i,j,A*(a[j].l-a[i].r)*(a[j].l-a[i].r)+B*(a[j].l-a[i].r)+C);
		}
	for (int i=1;i<=m;i++)
		if (a[i].u==1) Dij.AddEdge(S,i,A*a[i].l*a[i].l+B*a[i].l+C); 
	for (int i=1;i<=m;i++)
		if (a[i].v==n) Dij.AddEdge(i,T,a[i].r);
	Dij.dijkstra(S);
	printf("%d\n",Dij.d[T]);
	return 0;
}

评测结果