记录编号	138067	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]飞行计划	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	3.843 s
提交时间	2014-11-05 17:00:01	内存使用	3.93 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int SIZEN=2010,SIZEM=10010,SIZEGN=220010,INF=0x7fffffff/2;
int GN;//0~N-1
vector<pair<int,int> > c[SIZEGN];
int f[SIZEGN];
bool inq[SIZEGN];
queue<int> Q;
void addedge(int a,int b,int w){
	c[a].push_back(make_pair(b,w));
}
int SPFA(int S,int T){
	for(int i=0;i<GN;i++) f[i]=INF;
	memset(inq,0,sizeof(inq));
	while(!Q.empty()) Q.pop();
	f[S]=0;inq[S]=true;Q.push(S);
	while(!Q.empty()){
		int x=Q.front();Q.pop();inq[x]=false;
		for(int i=0;i<c[x].size();i++){
			int u=c[x][i].first;
			if(f[x]+c[x][i].second<f[u]){
				f[u]=f[x]+c[x][i].second;
				if(!inq[u]){
					inq[u]=true;
					Q.push(u);
				}
			}
		}
	}
	return f[T];
}
int N,M,C;
class EDGE{
public:
	int u,v,h,w;
	int l,r;
};
EDGE edges[SIZEM];
vector<int> legal[SIZEN];
int sum[SIZEN];
void unique(vector<int> &s){
	sort(s.begin(),s.end());
	int tot=0;
	for(int i=0;i<s.size();i++){
		if(!i||s[i]!=s[i-1]) s[tot++]=s[i];
	}
	while(s.size()>tot) s.pop_back();
}
void mark_legal_height(void){//计算每个节点的合法高度
	legal[0].push_back(0);
	legal[N-1].push_back(0);
	for(int i=0;i<M;i++){
		edges[i].l=edges[i].h-(C/2),edges[i].r=edges[i].h+(C/2);
		edges[i].l=max(edges[i].l,0);
		for(int j=edges[i].l;j<=edges[i].r;j++){
			legal[edges[i].u].push_back(j);
			legal[edges[i].v].push_back(j);
		}
	}
	for(int i=0;i<N;i++) unique(legal[i]);
	sum[0]=0;
	for(int i=1;i<N;i++) sum[i]=sum[i-1]+legal[i-1].size();
}
int hash1(int i,int j){//i处的第j个合法高度
	return sum[i]+j;
}
int hash2(int i,int h){//i处高度为h
	return sum[i]+lower_bound(legal[i].begin(),legal[i].end(),h)-legal[i].begin();
}
void makegraph(void){
	GN=sum[N-1]+legal[N-1].size();
	for(int i=0;i<N;i++){
		for(int j=0;j+1<legal[i].size();j++){
			//爬升有花费,下降没有
			addedge(hash1(i,j),hash1(i,j+1),(legal[i][j+1]-legal[i][j])*C);
			addedge(hash1(i,j+1),hash1(i,j),0);
		}
	}
	for(int i=0;i<M;i++){
		for(int j=edges[i].l;j<=edges[i].r;j++){
			int a=hash2(edges[i].u,j),b=hash2(edges[i].v,j);
			int w=(edges[i].h-j)*(edges[i].h-j)+edges[i].w;
			addedge(a,b,w);
			addedge(b,a,w);
		}
	}
}
void read(void){
	scanf("%d%d%d",&N,&M,&C);
	for(int i=0;i<M;i++){
		scanf("%d%d%d%d",&edges[i].u,&edges[i].v,&edges[i].h,&edges[i].w);
	}
}
int main(){
	freopen("nt2012_route.in","r",stdin);
	freopen("nt2012_route.out","w",stdout);
	read();
	mark_legal_height();
	makegraph();
	printf("%d\n",SPFA(hash1(0,0),hash2(N-1,0)));
	return 0;
}