正权单调求和最短路通用解法

对于所有最短路定义为 $d(e_1,e_2,e_3,\dots)=\sum_iw(e_i,e_{i+1})$ ，其中 $w(e_i,e_{i+1})$ 关于 $e_i$ 和 $e_{i+1}$ 的边权单调不减。

这种最短路都有了 $O(pn\log n)$ 的解法，其中 $p$ 是 $w(e_i,e_{i+1})$ 计算时间。

本题中 $w(e_1,e_2)$ 定义为 $\sum_{i\le k}c_iw_{e_1}^{a_i}w_{e_2}^{b_i}$ 。

朴素的想法是既然最短路跟边有关，那我们对于每条边求出最短路。

转移就是枚举该边的终点的出边。

但由于一个点可能非常多入边出边，每个都要枚举一遍，这不优秀， $O(m^2)$ 。

我们进一步剖析其性质，每条边相当于二元组 $(d_i,w_i)$ ， $(d_1,w_1)+w_2\to (d_1+w(w_1,w_2),w_2)$ 。

不难发现决策单调性，即只有 $d$ 比较小或者 $w$ 比较小的时候这条边可能有用，对于 $d_1\ge d_2$ 且 $w_1\ge w_2$ ，那么 $e_1$ 就没用了。

$d$ 是动态求出的，但 $w$ 是提前给定的，我们可以事先把每个点的出边按照 $w$ 排序，这样每条入边要么没用，要么对一个区间的边有用。

但最短路是一个动态的过程，按照普通决策单调性的写法我们没办法一下子知道那么多信息，所以我们需要一种适合的写法。

具体来说，我们每次将一条边出队的时候，我们至少知道它管辖的第一条边，那我们就只加入这条边。

同时我们在优先队列中记录每条边由哪条边更新而来，每次将这条边出队的时候将它的“后继”加入队列。

而找一条边所管辖的区间，是在我们确定了其 $d$ 之后，也就是出队时。

由于 $\text{dijkstra}$ 的过程， $d$ 是越来越大的，所以每次把这条边加进去要先比较一下它和上次有用的边的 $w$ ，若 $w\ge w_{pre}$ ，又已知 $d\ge d_{pre}$ ，那这条边就没用了，否则我们就需要从其他边手中“抢夺”一些管辖领地（这是因为每次加一条新边的时候我们钦定它一直管辖到结尾）。

我们对每个点维护一个栈结构，存储仍然有用的入边，该栈结构满足 $\forall i,d_i\le d_{i+1},w_i\ge w_{i+1}$ ，把入边的管辖范围记在入边本身上。

每次加一条新边的时候我们可能需要踢掉一些区间，这并不是因为它们不满足偏序关系，而是因为它们的管辖范围被清空了，我们只有找到真正的这条边管辖的区间的前面的区间的管辖者，才能确定这条边的区间左端点到底关到哪里。

我们可以写一个二分函数 $f(a,b)$ 来求出已知 $d_a,d_b$ 时，入边 $a,b$ 在这两条边的出点 $v_a$ 的出边的管辖范围分界点（为了方便，求的是 $b$ 边管辖的第一条边的编号）。

这样我们就可以通过该函数来从单调栈中弹掉一些被清空的元素，来确定最后的管辖范围。

直到踢不动了，那我们就找到了真正的前驱，此时我们就钦定新加进去的边管辖 $[f(a,b),+\infty)$ 区间的边，前驱管辖 $[st_a,f(a,b))$ 的边。

需要注意一些细节，比如说并不是只有松弛成功才将其加入队列，因为该点的加入影响着该点后继的加入，直接加入并不会影响 $O(m\log m)$ 的复杂度，还有即使该边出队时是 vis=1 状态也要更新完该边的后继再退出。

理一下流程：

初始把源点的出边 $d=0$ 加进去。
每次出队一条边的时候更新它的前驱的“下一条边”（无论这条边是不是第一次出队）upd()，若这条边是第一次出队，就去确定它的管辖区间的左端点，并钦定其右端点管辖到结尾 psh()。

upd() 的流程就是朴素的更新下一条边（若到了管辖范围结尾就不更新）。

psh() 的流程：

首先判断该边是否有用。
若有用，则找到它的管辖范围的左端点，由于需要找到真正的左端点，所以需要找到管辖范围真正的前面的范围，所以需要踢掉中间那些没有利用价值的假边，并清空假边的管辖范围。
将该边的管辖范围设置。

感觉讲的很混乱，贴一下代码：

#include<bits/stdc++.h>
#define F(i,a,b) for(int i(a),i##end(b);i<=i##end;i++)
#define sz(x) int(x.size())
#define pb emplace_back
#define push emplace
#define gc getchar
using namespace std;typedef long long ll;
int read() {
    int s=0;char c=gc(),w=0;
    while(c<'0'||c>'9') w|=c=='-',c=gc();
    while(c>='0'&&c<='9') s=s*10+(c^48),c=gc();
    return w?-s:s;
} const int N=2e5+5;vector<int> G[N],q[N];
ll a[N],b[N],c[N],d[N],Z[N],ans[N];int n,m,k,X[N],Y[N],st[N],ed[N],vis[N];
struct S {
    ll d;int x,pre;S(ll d=0,int x=0,int pre=0):d(d),x(x),pre(pre) {} 
    bool operator<(S y)const{return d>y.d;}
};priority_queue<S> Q;
ll P(ll x,ll y) {ll res=1;
    F(i,1,y) res*=x;return res;
}
ll w(ll x,ll y) {ll res=0;
    F(i,1,k) res+=c[i]*P(x,a[i])*P(y,b[i]);
    return res;
}
int fd(int x,int y) {//d[x]<d[y],Z[x]>Z[y],y第一个决策点 
    int v=Y[x],L=0,R=sz(G[v])-1,mid;
    while(L<=R) mid=L+R>>1,d[x]+w(Z[x],Z[G[v][mid]])>=d[y]+w(Z[y],Z[G[v][mid]])?R=mid-1:(L=mid+1);
    return L;
}
void psh(int x) {//把x这条边加到出点的决策区间 
    int y=Y[x];auto &q=::q[y];
    if(sz(q)&&Z[q.back()]<=Z[x]) return st[x]=1,ed[x]=0,void();
    while(sz(q)>1&&fd(q.back(),x)<=fd(q[sz(q)-2],q.back())) st[q.back()]=ed[q.back()]+1,q.pop_back();
    if(sz(q)) st[x]=fd(q.back(),x),ed[q.back()]=st[x]-1;
    else st[x]=0;ed[x]=sz(G[y])-1;q.pb(x);
}
void upd(int x) {//更新“下一条”x这条边的出点的出边
    if(st[x]>ed[x]) return;int y=G[Y[x]][st[x]];
    d[y]=min(d[y],d[x]+w(Z[x],Z[y]));
    Q.push(d[y],y,x),st[x]++;
}
int main() {freopen("path.in","r",stdin);freopen("path.out","w",stdout);
    n=read();m=read();k=read();
    F(i,1,k) a[i]=read(),b[i]=read(),c[i]=read();
    F(i,1,m) {
        X[i]=read();Y[i]=read();Z[i]=read();
        G[X[i]].pb(i);
    } F(i,1,n) sort(begin(G[i]),end(G[i]),[](int x,int y){return Z[x]<Z[y];}); 
    memset(ans,0x3f,sizeof ans);memset(d,0x3f,sizeof d);
    for(int x:G[1]) Q.push(d[x]=0,x,0);F(i,1,m) st[i]=1;
    while(!Q.empty()) {
        auto x=Q.top();Q.pop();
        if(x.pre) upd(x.pre);
        if(vis[x.x]) continue;vis[x.x]=1;
        psh(x.x);upd(x.x);
    } F(i,1,m) ans[Y[i]]=min(ans[Y[i]],d[i]);
    F(i,2,n) printf("%lld\n",ans[i]>1e18?-1ll:ans[i]);
    return 0;
}