一眼dijkstra

基本板子，我们发现对于一条边而言边权关于时间的函数$f(x)=c_i + \lfloor d_i/(t+1) \rfloor$先减后增。考虑$dijkstra$寻找$u->v$最优松弛的时间，令此时$u$的最短路长度为$dis(u)$，时间为$t$,显然此时$v$的最短路长度

$$dis(v) = t + c_i + \lfloor d_i/(t + 1) \rfloor (t >= dis(u) $$

考虑基本不等式

$$(t + 1) + d_i/(t + 1) -1 + c_i >= 2\sqrt d_i + c_i - 1 $$

当且仅当$(t + 1)^2 = d_i$时取等。我们都知道时光是不能倒流的即 $(dis(u) + 1)^2 <= d_i$满足时有取等条件。当无法满足取等条件时，观察到$dis$函数是单增的，于是我们取$t=dis(u)$ 我们得到一下丑陋的代码：

int tdis = c - 1 + (int)(sqrt(4 * d));
if((dis[u] + 1) > d / (dis[u] + 1))
	tdis = c + d / (dis[u] + 1) + dis[u];

注意乘法小心爆炸。 但是原式中有下取整，我们观察到$dis(v)$小数部分只在$2\sqrt d_i$中取到，把2放进去小数部分就一样了。 剩下的套个板子，注意$long long$

注意开小根堆

#include <bits/stdc++.h>
#define inf INT_MAX
#define NN INT_MIN
typedef long long ll;
#define int ll
using namespace std;
int n,m;
int dis[100005],vis[100005];
struct edge
{
	int u,v,c,d;
	int nxt;
}e[500005 << 2];
int head[500005],pos;
struct node
{
	int data,dis;
	bool operator >(const node &t) const
	{
		return dis > t.dis;
	}
};
void addEdge(int u,int v,int c,int d)
{
	e[++pos] = {u,v,c,d,head[u]};
	head[u] = pos;
}
void dijk(int s,int t)
{
	memset(dis,0x7f,sizeof dis);
	memset(vis,0,sizeof vis);
	priority_queue<node,vector<node>,greater<node> > q;
	dis[s] = 0;
	q.push({s,0});
	while(q.size())
	{
		node cur = q.top();
		int u = cur.data,dis1 = cur.dis;
		q.pop();
		if(vis[u])
			continue;
		vis[u] = 1;
		for(int i = head[u];i;i = e[i].nxt)
		{
			int v = e[i].v,c = e[i].c,d = e[i].d;
			int tdis = c - 1 + (int)(sqrt(4 * d));
			if((dis[u] + 1) > d / (dis[u] + 1))
				tdis = c + d / (dis[u] + 1) + dis[u];
			if(tdis < dis[v])
			{
				dis[v] = tdis;
				if(!vis[v])
					q.push({v,dis[v]});
			}
		}
	}
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n >> m ;
	for(int i = 1;i <= m;i++)
	{
		int u,v,c,d;
		cin >> u >> v >> c >> d ;
		addEdge(u,v,c,d);
		addEdge(v,u,c,d);
	}
	dijk(1,n);
	if(dis[n] > 10000000000000000)
		cout << -1 << endl ;
	else
		cout << dis[n] <<endl ;
	return 0;
}