记录编号	138059	评测结果	AAAAAAEEEEEEEEEEEEEE
题目名称	1794.[国家集训队2012]飞行计划	最终得分	30
用户昵称	cstdio	是否通过	未通过
代码语言	C++	运行时间	1.276 s
提交时间	2014-11-05 16:52:00	内存使用	0.90 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int SIZEN=2010,SIZEM=10010,INF=0x7fffffff/2;
class GRAPH{//大家好我是图
public://里世界
	static const int SIZEN=20010;
	int N;//0~N-1
	vector<pair<int,int> > c[SIZEN];
	int f[SIZEN];
	bool inq[SIZEN];
	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<N;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];
	}
}G;
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){
	G.N=sum[N-1]+legal[N-1].size();
	for(int i=0;i<N;i++){
		for(int j=0;j+1<legal[i].size();j++){
			//爬升有花费,下降没有
			G.addedge(hash1(i,j),hash1(i,j+1),(legal[i][j+1]-legal[i][j])*C);
			G.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;
			G.addedge(a,b,w);
			G.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",G.SPFA(hash1(0,0),hash2(N-1,0)));
	return 0;
}