// 分层图最短路 Dijkstra 算法 O(NlogN)
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;

const int N=6e5;
vector<pii> g[N],e[N];
int T,n,m,k;
int v[N],w[N],sw[N],cnt,a[N],l[N],r[N],d[N];
bool vis[N];

void dijkstra(){
  memset(d,0x3f,sizeof d),d[1]=0;
  priority_queue<pii,vector<pii>,greater<pii> > q;
  q.push({0,1});
  while(!q.empty()){
    int u=q.top().second; q.pop();
    if(vis[u])continue; vis[u]=1;
    for(auto [v,w]:e[u]){
      if(d[v]>d[u]+w){
        d[v]=d[u]+w;
        q.push({d[v],v});
      }
    }
  }
}
signed main(){
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  cin>>T>>n>>m>>k; //n个点，m条边，k为参数上限
  for(int i=1; i<k; i++) cin>>v[i]; //v增参费用
  for(int i=2; i<=k; i++) cin>>w[i],sw[i]=sw[i-1]+w[i];//sw减参费用前缀和
  for(int i=1; i<=n; i++){
    cin>>a[i]; //i点的出边数量
    l[i]=cnt,r[i]=cnt+a[i],cnt+=a[i]+1; //i点的出边编号范围[li,ri]
    for(int j=0,y,z; j<a[i]; j++) cin>>y>>z,g[i].emplace_back(y,z); //i向y连边
  }
  for(int i=1; i<=n; i++){
    for(int j=1; j<=a[i]; j++){
      auto [y,z]=g[i][j-1];
      if(j<=a[y]) e[l[i]+j].emplace_back(l[y]+j,z); //从 i 向 y 的同级拆点连边
      else{
        e[l[i]+j].emplace_back(l[y],z); //从i的第j拆点向y的第ly拆点连边，到ly不再移动
        if(a[y]) e[l[i]+j].emplace_back(r[y],z+sw[j]-sw[a[y]]); //从i的第j拆点向y的第ry拆点连边，到ry可继续移动
      }
      if(j>1){
        e[l[i]+j-1].emplace_back(l[i]+j,v[j-1]); //i点的相邻出边点连边，增参边权v
        e[l[i]+j].emplace_back(l[i]+j-1,w[j]);   //i点的相邻出边点连边，减参边权w
      }
    }
  }
  
  dijkstra();
  for(int i=1; i<=n; i++){
    int ans=*min_element(d+l[i],d+r[i]+1);
    cout<<(ans>1e18?-1:ans)<<' ';
  }
}

前言

比其他题解里的好写很多。

思路

首先看到的是 $n$ 个点 $m$ 条边，可以想到跑最短路。
然后发现还有一个限制 $p$，只能走每个点的第 $p$ 条边。
所以实际上是两个限制，第 $i$ 个点，限制为 $p$。
多个限制的最短路问题用分层图解决。

建图，根据题意点对点连边即可。

转移，分为两种：

1. 同一个点内转移，即 $i$ 不变，$p$ 变。
2. 不同点间转移，即 $i$ 变，$p$ 不变。

这样太麻烦了，不如每次转移 $i,p$ 一起变。具体而言，先变 $i$，再变 $p$。
变 $i$ 的时候 $p$ 没变，所以有一条路可以走，变完之后的 $i'$ 是确定的，花费也是确定的。
变后的 $p'$ 要能继续转移，所以不能大于 $d_{i'}$，在 $1\sim d_{i'}$ 内枚举 $p'$ 即可。
变 $p$ 产生的花费是 $v_i$ 或 $w_i$ 内某一段的和，可以用前缀和来维护。

不过有个例外，我们也可以只变 $i$，不变 $p$，并且之后不用这个状态转移了，那么 $p$ 是否大于 $d_{i'}$ 就不用关心。我们可以把这种例外全部看作 $p'=0$ 的特殊情况。

最后对每个 $i$，统计 $p$ 取 $0\sim d_i$ 花费的最小值即可。

时间复杂度为 $O((n+m)\log (n+m))$。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,pii> plii;
const int MAXN=3e5+3;
const ll Inf=1e18;

int n,m,k;
int v[MAXN],w[MAXN],d[MAXN];

vector<pii>edg[MAXN];
vector<ll>dis[MAXN];
vector<bool>vis[MAXN];
priority_queue<plii>q;

ll sumv[MAXN],sumw[MAXN];
ll change(int x,int y){
	if(x<y)return sumv[y-1]-sumv[x-1];
	else return sumw[x]-sumw[y];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int c; cin>>c>>n>>m>>k;
	for(int i=1;i<k;i++){
		cin>>v[i];
		sumv[i]=sumv[i-1]+v[i];
	}
	for(int i=2;i<=k;i++){
		cin>>w[i];
		sumw[i]=sumw[i-1]+w[i];
	}
	for(int i=1;i<=n;i++){
		cin>>d[i];
		edg[i].push_back({0,0});
		for(int j=1;j<=d[i];j++){
			int y,z; cin>>y>>z;
			edg[i].push_back({y,z});
		}
		for(int j=0;j<=d[i];j++){
			dis[i].push_back(Inf);
			vis[i].push_back(0);
		}
	}
	for(int i=1;i<=d[1];i++){
		dis[1][i]=change(1,i);
		q.push({-dis[1][i],{1,i}});
	}
	while(!q.empty()){
		pii pos=q.top().second; q.pop();
		int fr=pos.first,p=pos.second;
		if(vis[fr][p])continue;
		vis[fr][p]=1;
		int to=edg[fr][p].first;
		ll cost0=dis[fr][p]+edg[fr][p].second;
		dis[to][0]=min(dis[to][0],cost0);
		for(int i=1;i<=d[to];i++){
			ll cost=cost0+change(p,i);
			if(cost<dis[to][i]){
				dis[to][i]=cost;
				q.push({-cost,{to,i}});
			}
		}
	}
	for(int i=1;i<=n;i++){
		ll ans=Inf;
		for(int j=0;j<=d[i];j++)ans=min(ans,dis[i][j]);
		cout<<(ans==Inf?-1:ans)<<' ';
	}
	return 0;
}

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 300010;
int n, m, k, c, sumv[N], sumw[N], d[N];
struct Edge { int y, w;};
struct node {
    int x, eid,w;
    bool operator <(const node no) const {return w > no.w;}
};
vector<Edge>a[N];
vector<int>b[N];
map<int, int>dis[N];
map<int, bool>vis[N];
signed main() {

    scanf("%lld%lld%lld%lld", &c, &n, &m, &k);
    for (int i = 1,x; i < k; i++)scanf("%lld", &x),sumv[i] = sumv[i - 1] + x;
    for (int i = 2,x; i <= k; i++) scanf("%lld", &x),sumw[i] = sumw[i - 1] + x;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &d[i]);
        a[i].push_back({0,0});
        for (int j = 1, y, w ; j <= d[i]; j++) {
            scanf("%lld%lld", &y, &w);
            dis[y][j] = 1e18;
            vis[y][j] = false;
            b[y].push_back(j);
            a[i].push_back({y,w});
        }
    }

    priority_queue<node>q;
    q.push({1,1,0});
    dis[1][1] = 0;

    while (!q.empty()) {
        node no = q.top();q.pop();
        int x= no.x, eid = no.eid;

        if (vis[x][eid])continue;
        vis[x][eid] = 1;

        for (int i = 1; i <= d[x]; i++) {
            int y = a[x][i].y, res = 0;

            if (eid > i) res = sumw[eid] - sumw[i];
            else         res = sumv[i - 1] - sumv[eid - 1];

            if (dis[y][i] > dis[x][eid] + res + a[x][i].w) {
                dis[y][i] = dis[x][eid] + res + a[x][i].w;
                if (!vis[y][i]) q.push({y,i,dis[y][i]});
            }
        }
    }
    printf("0 ");
    for (int i = 2; i <= n; i++) {
        int ans = 1e18;
        for (int j = 0; j < b[i].size(); j++)  ans = min(ans, dis[i][b[i][j]]);
        if (ans == 1e18)ans = -1;
        printf("%lld ", ans);
    }
    return 0;
}