Gioush OJ
⌕ 题目搜索注册登录
P1028 · OFFICIAL SOLUTION

P1028 灵舵渡千屿 官方题解

Gioush OJ · P1028 灵舵渡千屿

灵舵渡千屿

【题意简述】

有一张有向图，每个点的出边有固定编号。当前档位为 pp 时，只能走当前点的第 pp 条出边；也可以花费代价把 pp 调高或调低。初始在点 11，档位为 11，求到每个点的最小代价。

【Hint】

朴素状态是 (u,p)(u,p)。但对点 uu，只有 1≤p≤du1\le p\le d_u 的状态会继续向外走，因此总状态数是 ∑du=m\sum d_u=m 级别。

【提示】

将每个点拆成 dud_u 个档位状态，同点相邻档位之间连调档边，第 jj 条出边从 (u,j)(u,j) 连到目标点对应的档位状态。

【解法】

建立分层图。状态 (u,j)(u,j) 表示当前在点 uu，档位为 jj。对于同一个点，有

(u,j)→(u,j+1),cost=vj,(u,j)\to(u,j+1),\quad \text{cost}=v_j, (u,j)→(u,j−1),cost=wj.(u,j)\to(u,j-1),\quad \text{cost}=w_j.

若 uu 的第 jj 条出边为 u→yu\to y，边权为 zz：

  • 若 j≤dyj\le d_y，连到 (y,j)(y,j)，代价为 zz；
  • 若 j>dyj>d_y，可以先到 yy 后把档位降到 dyd_y，代价增加一段下调前缀和。

在这张图上从 (1,1)(1,1) 跑 Dijkstra。每个原点的答案是其所有拆点状态距离的最小值；若没有状态可达，则输出 −1-1。

【状态与边】

对原点 uu 的第 jj 个档位建立状态 (u,j)(u,j)。相邻档位之间的两条边恰好表示升、降档的代价；第 jj 条原图出边则从 (u,j)(u,j) 转移到对应目标状态。若到达目标点后的档位超过其出度，先连续下调到最后一个可用档位，这段代价由下调前缀和一次给出。

每条真实行走与调档序列都对应拆点图中的一条路径；反过来，拆点图每条边也都是允许操作。因此最短路与原问题最小代价完全等价。

【复杂度】

状态数为 ∑udu=m\sum_u d_u=m 级别，边数同阶。Dijkstra 复杂度为 O((n+m)log⁡(n+m))\mathcal{O}((n+m)\log(n+m))。

【参考代码】

#include <queue>#include <vector>#include <cstdio>#include <cstring>#include <algorithm>#define MAXN 600100#define MAXM 300100#define MAXK 250100using namespace std;int Head[MAXN],Total=0,S,n,m,Deg[MAXN],cnt=0,k;int St[MAXM],Ed[MAXM],cne=0,Tag[MAXM],Back[MAXN];long long Dist[MAXN<<1],Pre[MAXK],Ans[MAXN],UpValue[MAXK],DownValue[MAXK],EdgeV[MAXM];bool Visited[MAXN];vector <int> Mark[MAXN];struct edge{    int St,Ed;    int Next;    long long Value;}Edge[MAXM<<2];void Edge_Add(int a,int b,long long Value){    Edge[++Total]={a,b,Head[a],Value};    Head[a]=Total;}priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> Q;void Dijkstra(){    memset(Dist,0x3f,sizeof(Dist));    Q.emplace(0,S);Dist[S]=0;    while(!Q.empty()){        int Now=Q.top().second;Q.pop();        if(Visited[Now]) continue;        Visited[Now]=true;        for(int i=Head[Now];i;i=Edge[i].Next){            int To=Edge[i].Ed;            if(Dist[To]>Dist[Now]+Edge[i].Value){                Dist[To]=Dist[Now]+Edge[i].Value;                Q.emplace(Dist[To],To);            }        }    }} int main(){    freopen("helm.in","r",stdin);    freopen("helm.out","w",stdout);    memset(Ans,0x3f,sizeof(Ans));    Pre[1]=0;    scanf("%d%d%d",&n,&m,&k);    for(int i=1;i<=k-1;i++){        scanf("%lld",&UpValue[i]);    }    for(int i=2;i<=k;i++){        scanf("%lld",&DownValue[i]);        Pre[i]=DownValue[i]+Pre[i-1];    }    for(int i=1;i<=n;i++){        scanf("%d",&Deg[i]);        cnt++;        Mark[i].push_back(cnt);        Back[cnt]=i;        for(int j=1;j<=Deg[i];j++){            cnt++;            Mark[i].push_back(cnt);            Back[cnt]=i;            if(j!=1){                Edge_Add(Mark[i][j],Mark[i][j-1],DownValue[j]);                Edge_Add(Mark[i][j-1],Mark[i][j],UpValue[j-1]);            }        }        for(int j=1;j<=Deg[i];j++){            cne++;            scanf("%d%d",&Ed[cne],&EdgeV[cne]);            Tag[cne]=j;St[cne]=i;        }    }    S=Mark[1][Deg[1]?1:0];    for(int i=1;i<=m;i++){        if(!Deg[Ed[i]]){            Edge_Add(Mark[St[i]][Tag[i]],Mark[Ed[i]][0],EdgeV[i]);        }        else if(Deg[Ed[i]]<Tag[i]){            cnt++;Mark[Ed[i]].push_back(cnt);Back[cnt]=Ed[i];            Edge_Add(Mark[St[i]][Tag[i]],cnt,EdgeV[i]);            Edge_Add(cnt,Mark[Ed[i]][Deg[Ed[i]]],                     Pre[Tag[i]]-Pre[Deg[Ed[i]]]);        }        else{            Edge_Add(Mark[St[i]][Tag[i]],Mark[Ed[i]][Tag[i]],EdgeV[i]);        }    }    Dijkstra();    Ans[1]=0;    for(int i=1;i<=cnt;i++){        Ans[Back[i]]=min(Ans[Back[i]],Dist[i]);    }    for(int i=1;i<=n;i++){        if(Ans[i]==0x3f3f3f3f3f3f3f3f){            printf("-1 ");        }        else printf("%lld ",Ans[i]);    }    return 0;}