rt 以下是代码
record
思路是每次取出最小边并更新
询问复杂度哪里伪了|求条

#include<bits/stdc++.h>
#define int long long
#define maxn 200005
using namespace std;
int n,m;
int x[maxn];
int read(){
	int x=0;char ch;
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}
void write(int x){
	char sta[25],top=0;
	do{
		sta[++top]=x%10+'0';
		x/=10;
	}while(x);
	for(int i=top;i>=1;i--)putchar(sta[i]);
}
struct train_type{
	int s,t,B,num;
	bool operator < (const train_type &other)const{
		return s>other.s;
	}
}First; 
bool cmp(train_type x,train_type y){
	return x.s<y.s;
}
int vis[maxn],inqueue[maxn];
vector<train_type>to[maxn];
signed main(){
	cin>>n>>m>>x[1];
	for(int i=1;i<=m;i++){
		int a,b,s,t;
		a=read();b=read();
		s=read();t=read();
		to[a].push_back({s,t,b,i});
		if(i==1)First={s,t,b,i};
	}
	priority_queue<train_type>pq;
	pq.push(First);
	for(int i=1;i<=n;i++)sort(to[i].begin(),to[i].end(),cmp);
	while(pq.size()){
		train_type now=pq.top();pq.pop();
		if(vis[now.num])continue;
		vis[now.num]=1;
		train_type xxx={now.t};
		int start=lower_bound(to[now.B].begin(),to[now.B].end(),xxx,cmp)-to[now.B].begin();
		for(int i=start;i<to[now.B].size();i++){
			train_type it=to[now.B][i];
			x[it.num]=max(x[it.num],x[now.num]+now.t-it.s);
			if(!inqueue[it.num])pq.push(it);
			inqueue[it.num]=1;
		}
	} 
	for(int i=2;i<=m;i++){
		write(x[i]);
		putchar(' ');
	}
	return 0;
}