【LOJ#3156】【NOI2019】—回家路線

傳送門

明明可以 b f s bfs bfs寫了個 d i j dij dij把自己強行玩 w a wa wa

有2種做法

第一種：

考慮對于同一個點的入邊 i , j i,j i,j轉移給出邊 x x x

把式子列出來後發現是一個标準的斜率優化

在凸包上二分就可以了

複雜度 O ( m l o g m ) O(mlogm) O(mlogm)

第二種：

發現時間很小

f [ i ] [ j ] f[i][j] f[i][j]表示在點 i i i時間 j j j時最小值

用 m a p map map存一下暴力轉移也可以過

複雜度 O ( m k l o g k ) ， k O(mklogk)，k O(mklogk)，k是最大的時間

常數很小也可以卡過

UPDATE

好像是原題簡化版

算了 C C F CCF CCF都讓人家出題人做綠皮火車了也不奢求什麼了

#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<21|1;
inline char gc(){
    static char ibuf[RLEN],*ib,*ob;
    (ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
    return (ib==ob)?EOF:*ib++;
} 
#define gc getchar
inline int read(){
    char ch=gc();
    int res=0,f=1;
    while(!isdigit(ch))f^=ch=='-',ch=gc();
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
    return f?res:-res;
}
#define re register 
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define pob pop_back
#define pf push_front
#define pof pop_front
const int N=100005,M=200005;
int n,m;
ll A,B,C;
const ll inf=1e15;
map<int,ll> f[N];
#define IT map<int,ll>::iterator
struct node{
	int x,y,p,q;
	friend inline bool operator <(const node &a,const node &b){
		return a.p<b.p;
	}
}p[M];
inline ll calc(ll x){
	return A*x*x+B*x+C;
}
int main(){
	n=read(),m=read(),A=read(),B=read(),C=read();
	for(int i=1;i<=m;i++){
		p[i].x=read(),p[i].y=read(),p[i].p=read(),p[i].q=read();
		f[p[i].y][p[i].q]=inf;
	}
	sort(p+1,p+m+1);
	f[1][0]=0;
	for(int i=1;i<=m;i++){
		for(IT it=f[p[i].x].begin();it!=f[p[i].x].end();it++){
			if((*it).fi>p[i].p)break;
			if((*it).se==inf)continue;
			int x=p[i].p-(*it).fi;
			ll res=calc(x);
			if(f[p[i].y][p[i].q]>(*it).se+res)f[p[i].y][p[i].q]=(*it).se+res;
		}
	}
	ll res=inf;
	for(IT it=f[n].begin();it!=f[n].end();it++)res=min(res,(*it).fi+(*it).se);
	cout<<res;
}