这篇题解的背景
看蓝书的时候感觉这题挺模板所以不太想做,然而上午李赛(特指某全国名校某金牌教练组织的比赛)里出现了这题,所以写篇题解纪念下吧。
题目描述
一张无向图中有 $N$ 个点,给定 $M$ 个操作(以下用 $m_1,m_2,…,m_n$ 表示),如果来到当前结点时使用的操作为 $m_i$,下一步可以花费 $ |2\times m_j| + |j-i|$ 的代价移动 $m_j$ 个单位,也可以花费 $|2\times m_i|$ 的代价移动 $m_i$ 个单位,求从 $1$ 号点到 $N$ 号点的最少代价。
解法
可以发现,本题中每一次移动的代价都受到上一次移动的影响,因此每次移动的代价都是无法确定的。此时显然无法使用朴素的最短路算法解题。
考虑在普通最短路算法的基础上进行一些改进。注意到每次操作只受到前一次操作的影响,所以不妨记录上一次移动使用的操作序号,即使用 $dis_{i,j}$ 表示当前结点为 $i$,转移到当前结点使用的操作为 $j$ 的最短路。
这样一来,我们就可以用分层图最短路$^{(1)}$解决本题。把整张图分为 $M$ 层,算法结束后,最终答案即为 $max\{\space dis_{n,i}\space,\space i\in [1,M]\space \}$。
本题中不存在负权,更不可能有负环,因此最短路问题中常用的 $Dijkstra$ 与 队列优化的 $Bellman-Ford$ 两种算法都可以使用。下面分别给出两种算法的代码实现。
C++ 代码
Dijkstra
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int dis[1010][30],n,m,c[30],h[1010],tot=1,st;
bool vis[1010][30];
struct asdf{
int v,w,nxt;
}e[40086];
struct node{
int no,dis,lstw;
node(){}
node(int noo,int diss,int lstww){no=noo;dis=diss;lstw=lstww;}
bool operator <(const node &b)const{return dis>b.dis;}
};
priority_queue<node>q;
int Abs(int x){return x<0?-x:x;}
int Min(int a,int b){return a<b?a:b;}
bool add(int u,int v,int w){
e[++tot].v=v;
e[tot].w=w;
e[tot].nxt=h[u];
h[u]=tot;
return true;
}
bool solve(int s){
dis[s][st]=0;
q.push(node(s,0,st));
while(!q.empty()){
node tp=q.top();
int np=tp.no,lw=tp.lstw;
q.pop();
if(tp.dis!=dis[np][lw])continue;
for(int i=h[np];i;i=e[i].nxt){
if(!c[e[i].w]){
if(!dis[np][lw])continue;
int ndis=Abs(c[lw])*2,v=np+c[lw];
if(v<1||v>n||dis[np][lw]+ndis>=dis[v][lw])continue;
dis[v][lw]=dis[np][lw]+ndis;
q.push(node(v,dis[v][lw],lw));
continue;
}
int ndis=Abs(c[e[i].w])*2+Abs(e[i].w-lw);
if(dis[np][lw]+ndis<dis[e[i].v][e[i].w]){
dis[e[i].v][e[i].w]=dis[np][lw]+ndis;
q.push(node(e[i].v,dis[e[i].v][e[i].w],e[i].w));
}
}
}
return true;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d",c+i);
for(int j=1;j<=n;j++){
dis[j][i]=0x3f3f3f3f;
if(j+c[i]>0&&j+c[i]<=n)
if(c[i])add(j,j+c[i],i);
else add(j,j,0),st=i;
}
}
solve(1);
int ans=0x3f3f3f3f;
for(int i=1;i<=m;i++)
ans=Min(ans,dis[n][i]);
if(ans!=0x3f3f3f3f)printf("%d",ans);
else printf("-1");
}
队列优化 Bellman-Ford
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int dis[1010][30],n,m,c[30],h[1010],tot=1,st;
bool vis[1010][30];
struct asdf{
int v,w,nxt;
}e[40086];
struct node{
int no,lstw;
node(){}
node(int noo,int lstww){no=noo;lstw=lstww;}
};
queue<node>q;
int Abs(int x){return x<0?-x:x;}
int Min(int a,int b){return a<b?a:b;}
bool add(int u,int v,int w){
e[++tot].v=v;
e[tot].w=w;
e[tot].nxt=h[u];
h[u]=tot;
return true;
}
bool solve(int s){
dis[s][st]=0;
q.push(node(s,st));
while(!q.empty()){
node tp=q.front();
int np=tp.no,lw=tp.lstw;
q.pop();
vis[np][lw]=false;
for(int i=h[np];i;i=e[i].nxt){
if(!c[e[i].w]){
if(!dis[np][lw])continue;
int ndis=Abs(c[lw])*2,v=np+c[lw];
if(v<1||v>n||dis[np][lw]+ndis>=dis[v][lw])continue;
dis[v][lw]=dis[np][lw]+ndis;
if(vis[v][lw])continue;
vis[v][lw]=true;
q.push(node(v,lw));
continue;
}
int ndis=Abs(c[e[i].w])*2+Abs(e[i].w-lw);
if(dis[np][lw]+ndis<dis[e[i].v][e[i].w]){
dis[e[i].v][e[i].w]=dis[np][lw]+ndis;
if(vis[e[i].v][e[i].w])continue;
vis[e[i].v][e[i].w]=true;
q.push(node(e[i].v,e[i].w));
}
}
}
return true;
}
int main(){
memset(dis,0x3f3f3f3f,sizeof(dis));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d",c+i);
for(int j=1;j<=n;j++)
if(j+c[i]>0&&j+c[i]<=n)
if(c[i])add(j,j+c[i],i);
else add(j,j,0),st=i;
}
solve(1);
int ans=0x3f3f3f3f;
for(int i=1;i<=m;i++)
ans=Min(ans,dis[n][i]);
if(ans!=0x3f3f3f3f)printf("%d",ans);
else printf("-1");
}
注释
$\tiny{(1)}$ 分层图最短路:相关内容参见蓝书 0x61
节,书中的例题为 AcWing340 通信线路,如想要进一步练习,可尝试解决此题。
我没有判if ( !c[e[i].w] ) 那个,也可以ac,这个判断部分是不是多余了
%%%
李赛可还行
杨神!
$stO$
%%%