题解

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define int long long 
using namespace std;
using namespace __gnu_pbds;
constexpr int N=3e5+1;
int id,n,m,k,v[N],w[N],oud[N],ans[N];
gp_hash_table<int,int>dis[N],vis[N];
vector<pair<int,int> >e[N];
void add(int u,int v,int w){
    e[u].push_back({v,w});
    return;
}
int up(int x,int y){
    return v[y-1]-v[x-1];
}
int down(int x,int y){
    return w[x]-w[y];
}
void dijkstra(){
    std::priority_queue<pair<int,pair<int,int> >,vector<pair<int,pair<int,int> > >,greater<pair<int,pair<int,int> > > >q;
    q.push({dis[1][1]=0,{1,1}});
    ans[1]=0;
    while(!q.empty()){
        auto[d,H17]=q.top();
        auto[u,p]=H17;
        q.pop();
        if(dis[u][p]!=d)
            continue;
        for(int i=1;i<=min(oud[u],p-1);i++)
            if(!vis[u][i]||d+down(p,i)<dis[u][i]){
                q.push({dis[u][i]=d+down(p,i),{u,i}});
                ans[u]=min(ans[u],dis[u][i]);
                vis[u][i]=1;
            }
        for(int i=p+1;i<=min(oud[u],k);i++)
            if(!vis[u][i]||d+up(p,i)<dis[u][i]){
                q.push({dis[u][i]=d+up(p,i),{u,i}});
                ans[u]=min(ans[u],dis[u][i]);
                vis[u][i]=1;
            }
        if(oud[u]<p)
            continue;
        auto[v,w]=e[u][p-1];
        if(!vis[v][p]||d+w<dis[v][p]){
            q.push({dis[v][p]=d+w,{v,p}});
            ans[v]=min(ans[v],dis[v][p]);
            vis[v][p]=1;
        }
    }
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin>>id>>n>>m>>k;
    for(int i=1;i<k;i++){
        cin>>v[i];
        v[i]+=v[i-1];
    }
    for(int i=2;i<=k;i++){
        cin>>w[i];
        w[i]+=w[i-1];
    }
    for(int u=1,v,w;u<=n;u++){
        cin>>oud[u];
        for(int i=1;i<=oud[u];i++){
            cin>>v>>w;
            add(u,v,w);
        }
    }
    memset(ans,0x3f,sizeof(ans));
    dijkstra();
    for(int i=1;i<=n;i++)
        cout<<(ans[i]!=0x3f3f3f3f3f3f3f3fll?ans[i]:-1)<<' ';
    return 0;
}