C++14(g++5.4) 解法, 执行用时: 717ms, 内存消耗: 8048K, 提交时间: 2020-05-30 19:38:01

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,l,r,d[N],vis[N];
int head[N],nex[N],to[N],K[N],B[N],tot;
inline void add(int a,int b,int c,int d){
	to[++tot]=b; nex[tot]=head[a]; K[tot]=c; B[tot]=d; head[a]=tot;
}
priority_queue<pair<int,int> > q;
inline int check(int mid){
	q.push({0,1}); memset(d,0x3f,sizeof d); d[1]=0; memset(vis,0,sizeof vis);
	while(q.size()){
		int u=q.top().second; q.pop();
		if(vis[u]) continue; vis[u]=1;
		for(int i=head[u];i;i=nex[i]) if(d[to[i]]>d[u]+K[i]*mid+B[i]){
			d[to[i]]=d[u]+K[i]*mid+B[i];	q.push({-d[to[i]],to[i]});
		}
	}
	return d[n];
}
signed main(){
	cin>>n>>m>>r;
	for(int i=1,a,b,c,d;i<=m;i++)	scanf("%lld %lld %lld %lld",&a,&b,&c,&d),add(a,b,c,d);
	while(l+10<r){
		int midr=r-(r-l)/3,midl=l+(r-l)/3;
		if(check(midl)>check(midr))	r=midr;
		else	l=midl;
	}
	int res=0; 
	for(int i=l;i<=r;i++)	res=max(res,check(i));
	cout<<res;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 443ms, 内存消耗: 10600K, 提交时间: 2020-06-26 13:45:41

#include<bits/stdc++.h>
using namespace std;

struct node
{
	long long x,h;
	bool operator<(const node &a)const
	{
		return a.h<h;
	}
}r,f;
priority_queue<node>Q;
vector<int>R[120005],ID[120005];
long long ans=0,D[120005];
int n,m,H,k[120005],b[120005];
long long dij(long long x)
{
	long long i,j,id;
	for(i=1;i<=n;i++)D[i]=2e18;
	r.x=1,D[1]=r.h=0,Q.push(r);
	while(!Q.empty())
	{
		f=Q.top(),Q.pop();
		if(D[f.x]<f.h)continue;
		for(i=0;i<R[f.x].size();i++)
		{
			j=R[f.x][i],id=ID[f.x][i];
			if(f.h+k[id]*x+b[id]<D[j])r.h=D[j]=f.h+k[id]*x+b[id],r.x=j,Q.push(r);
		}
	}
	return D[n];
}
int main()
{
    int i,u,v,l,r,m1,m2;
    scanf("%d%d%d",&n,&m,&H);
    for(i=1;i<=m;i++)
    {
    	scanf("%d%d%d%d",&u,&v,&k[i],&b[i]);
    	R[u].push_back(v),ID[u].push_back(i);
	}
	for(l=0,r=H;r-l>2;)
	{
		m1=l+(r-l)/3,m2=r-(r-l)/3;
		if(dij(m1)<dij(m2))l=m1;
		else r=m2;
	}
	while(l<=r)ans=max(ans,dij(l++));
	printf("%lld\n",ans);
}