好像所有的题解都是同一种思路，但是都没有好好说明白复杂度……AcWing 上这题题解区倒是有人说了，但是有说拆点后边数规模是 1e4 的，有说复杂度是 $O((N+M)logN)$ 的，甚至还有说是 $O(NlogN)$ 的……

个人认为应该是 $O(Q·C(N+M)·log(CN))$，我看到讨论区有人也是这么想的

然而这样的复杂度肯定是过不去本题的，说不定可以造一组数据卡掉所有的题解

所以我整了这样的数据：$N=1000$，从每个点向其后面的 $10$ 个点连边，边权为两点编号之差的绝对值

之后查询 $100$ 次，每次都从 $1$ 到 $N$，油箱容量 $100$

然后我测了一下，发现如果不开 O2 所有题解都会 TLE

不排除是我造的数据出锅了的缘故……所以放一下生成数据用的代码

#include<cstdio>
#include<cstdlib>
#include<ctime>
using namespace std;
int n=1000,m=10000,q=100;
int Min(int a,int b){return a<b?a:b;}
int main(){
	freopen("test.in","w",stdout);
	printf("%d %d\n",n,m);
	for(int i=1;i<=n;i++)
		printf("1 ");
	putchar('\n');
	for(int i=1;i<n;i++)
		for(int j=1;j<=10;j++)
			printf("%d %d %d\n",i,Min(i+j,n),j);
	for(int i=1;i<=10;i++)printf("%d %d %d\n",n-1,n,i);
	printf("%d\n",q);
	for(int i=1;i<=q;i++){
		printf("%d %d %d\n",100,1,n);
	}
}