题意

求从 $1$ 走到每一个 $i(1\le i\le n)$ 的最短路，不过边有点限制而已。

解析

比较典型的分层图类型最短路。其实按理说它并不是类似于飞行路线一样的分层图最短路，它涉及同一个点之间的互相转移，这里定义「$x$ 号点 $y$ 状态」表示题目中说的从 $x$ 出发的第 $y$ 条边。

发现这种最短路不好维护点，考虑维护边，考虑给这 $m$ 条边标号为 $1∼m$，并定义 $dis_i$ 表示从 $1$ 号点 $1$ 状态到 $x$ 号点 $y$ 状态的代价最小值，其中 $x$ 号点 $y$ 状态的编号是 $i$，这样的最短路是很好维护的。

那么接下来考虑我们维护出的 $dis_i$ 是什么意思，它指的是从 $1$ 号点 $1$ 状态到 $x$ 号点 $y$ 状态的最小代价，那么也就意味着此时在 $x$ 号点，则这种维护边的最短路同时也维护了点，枚举每一条边，可知答案为：

其中，$edge\_start$ 表示每条边的起点。

接下来考虑怎么连边，比较容易的是对于每条边 $u\rightarrow v$，意义是从 $u$ 号点 $p$ 状态到 $v$ 号点 $p$ 状态，然后还有同一个点不同状态的转移，这其实也是容易的，将题目中的 $w$ 和 $v$ 做一下前缀和即可快速实现同一个点不同状态的转移，具体实现可以看代码。

注意这里我为了偷懒如果 $v$ 号点没有第 $p$ 条边我也正常连了边，但这样没有影响，因为最后我们只会枚举输入的 $m$ 条边统计答案。

CODE

#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios::sync_with_stdio(0), cin.tie(0)
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define pre(i, j, k) for(int i = j; i >= k; --i)
#define pb emplace_back
#define PII pair<int, int>
#define fi first
#define se second
#define fv inline void
#define int long long
using i32 = long long;
using i64 = __int128;
using u32 = unsigned long long;

const int N = 1e6 + 5;
const int mod = 998244353;

#define cmax(a, b) (a = a > b ? a : b)
#define cmin(a, b) (a = a < b ? a : b)
#define cadd(a, b) (a = ((a + b) % mod + mod) % mod)
#define cdel(a, b) (a = ((a - b) % mod + mod) % mod)

i32 testid, n, m, k, x, u, v, w, tt;
i32 dis[N], vis[N], out[N], add[N], del[N], ans[N], id[N];
vector<PII> e[N];
vector<int> g[N];
map<i32, i32> mp[N];
struct node {
    i32 dis, u;
    bool operator < (const node &a) const {
        return dis > a.dis;
    }
};
fv dij(int s) {
	rep(i, 1, tt) dis[i] = 1e16;
    priority_queue<node> q; dis[s] = 0; q.push({0, s});
    while(q.size()) {
        int u = q.top().u; q.pop();
        if(vis[u]) continue; vis[u] = 1;
        for(auto ed : e[u]) {
            int v = ed.fi, w = ed.se;
            if(dis[v] > dis[u] + w) dis[v] = dis[u] + w, q.push({dis[v], v});
        }
    }
}
signed main() {
    //freopen("robot.in","r",stdin);
    //freopen("robot.out"."w".stdout);
    FASTIO;
    cin >> testid;
    cin >> n >> m >> k;
    rep(i, 1, k - 1) cin >> add[i], add[i] += add[i - 1];
    rep(i, 2, k) cin >> del[i], del[i] += del[i - 1];
    rep(i, 1, n) {
        cin >> out[i], ans[i] = 1e16;
        rep(j, 1, out[i]) {
        	cin >> v >> w;
        	if(!mp[i][j]) mp[i][j] = ++tt, id[tt] = i, g[i].pb(j);
        	if(!mp[v][j]) mp[v][j] = ++tt, id[tt] = v, g[v].pb(j);
            e[mp[i][j]].pb(mp[v][j], w);
        }
    }
    rep(i, 1, n) sort(g[i].begin(), g[i].end());
	rep(i, 1, n) {
		if(g[i].size() < 2) continue;
		rep(j, 1, g[i].size() - 1) e[mp[i][g[i][j]]].pb(mp[i][g[i][j - 1]], del[g[i][j]] - del[g[i][j - 1]]), e[mp[i][g[i][j - 1]]].pb(mp[i][g[i][j]], add[g[i][j] - 1] - add[g[i][j - 1] - 1]);
	}
    dij(1); 
    i32 ret = 0;
    rep(i, 1, tt) cmin(ans[id[i]], dis[i]);
    rep(i, 1, n) if(ans[i] == 1e16) ans[i] = -1;
    rep(i, 1, n) cout << ans[i] << ' ';
    return 0;
}