前置知识
解法
考虑对票建虚点，从 \(c_{i}\) 向 \(i+n\) 连一条权值为 \(p_{i}\) 的边，然后从 \(i+n\) 向 \([a_{i},b_{i}]\) 连一条权值为 \(0\) 的边。
建出反图后 \(1 \to i\) 和 \(n \to i\) 的路径集合会有重复统计的部分，不妨以 \(dis_{1,i}+dis_{n,i}\) 作为初始值然后再进行一遍松弛操作（若没有重复部分就不需要松弛了）。
然后就是线段树优化建图板子了。
代码
struct SMT_Q_BG
{
ll id[900010],dis[2][900010],d[900010],vis[900010];
vector<pair<ll,ll> >e[900010];
ll lson(ll x)
{
return x*2;
}
ll rson(ll x)
{
return x*2+1;
}
void build(ll rt,ll l,ll r,ll n)
{
e[rt+n*4].push_back(make_pair(rt,0));
if(l==r)
{
id[l]=rt;
return;
}
e[lson(rt)].push_back(make_pair(rt,0));
e[rson(rt)].push_back(make_pair(rt,0));
e[rt+n*4].push_back(make_pair(lson(rt)+n*4,0));
e[rt+n*4].push_back(make_pair(rson(rt)+n*4,0));
ll mid=(l+r)/2;
build(lson(rt),l,mid,n);
build(rson(rt),mid+1,r,n);
}
void update(ll rt,ll l,ll r,ll x,ll y,ll pos,ll w,ll n)
{
if(x<=l&&r<=y)
{
e[rt].push_back(make_pair(pos+n*8,w));
return;
}
ll mid=(l+r)/2;
if(x<=mid)
{
update(lson(rt),l,mid,x,y,pos,w,n);
}
if(y>mid)
{
update(rson(rt),mid+1,r,x,y,pos,w,n);
}
}
void dijkstra1(ll s,ll id)
{
memset(vis,0,sizeof(vis));
memset(dis[id],0x3f,sizeof(dis[id]));
priority_queue<pair<ll,ll> >q;
dis[id][s]=0;
q.push(make_pair(-dis[id][s],s));
while(q.empty()==0)
{
ll x=q.top().second;
q.pop();
if(vis[x]==0)
{
vis[x]=1;
for(ll i=0;i<e[x].size();i++)
{
if(dis[id][e[x][i].first]>dis[id][x]+e[x][i].second)
{
dis[id][e[x][i].first]=dis[id][x]+e[x][i].second;
q.push(make_pair(-dis[id][e[x][i].first],e[x][i].first));
}
}
}
}
}
void dijkstra2(ll n,ll k)
{
memset(vis,0,sizeof(vis));
priority_queue<pair<ll,ll> >q;
for(ll i=1;i<=8*n+k;i++)
{
d[i]=dis[0][i]+dis[1][i];
q.push(make_pair(-d[i],i));
}
while(q.empty()==0)
{
ll x=q.top().second;
q.pop();
if(vis[x]==0)
{
vis[x]=1;
for(ll i=0;i<e[x].size();i++)
{
if(d[e[x][i].first]>d[x]+e[x][i].second)
{
d[e[x][i].first]=d[x]+e[x][i].second;
q.push(make_pair(-d[e[x][i].first],e[x][i].first));
}
}
}
}
}
}T;
int main()
{
ll n,k,c,p,a,b,i;
cin>>n>>k;
T.build(1,1,n,n);
for(i=1;i<=k;i++)
{
cin>>c>>p>>a>>b;
T.e[i+n*8].push_back(make_pair(T.id[c]+n*4,p));
T.update(1,1,n,a,b,i,0,n);
}
T.dijkstra1(T.id[1],0);
T.dijkstra1(T.id[n],1);
T.dijkstra2(n,k);
for(i=1;i<=n;i++)
{
cout<<(T.d[T.id[i]]<1e15?T.d[T.id[i]]:-1)<<endl;
}
return 0;
}