Part 3.2 广度优先搜索
1.BFS +优先队列优化
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
template <typename Tp>
void read(Tp &x){
char c=getchar();x=0;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;
}//快速读入，不解释
struct node{
int x,y,c,w;
bool operator <(node b)const{//const不可丢
return w>b.w;
}//因为STL中优先队列默认取出最大的元素
//所以这里重载运算符，保证每次取出的是最小代价的
};
priority_queue<node>q;//node类型必须定义<
int dx[]={0,1,0,-1,1,1,-1,-1,0,2,0,-2};//12方向及魔法代价
int dy[]={1,0,-1,0,1,-1,1,-1,2,0,-2,0};
int dw[]={0,0,0,0,2,2,2,2,2,2,2,2};
int a[105][105],dis[105][105];//a存储棋盘上格子的颜色
int n,m;
void bfs(){
memset(dis,0x3f,sizeof(dis));dis[1][1]=0;
q.push((node){1,1,a[1][1],dis[1][1]});
node cur,nxt;
while(!q.empty()){
cur=q.top();q.pop();
if(dis[cur.x][cur.y]<cur.w)continue;
for(int i=0;i<12;i++){//懒惰删除
nxt.x=cur.x+dx[i];
nxt.y=cur.y+dy[i];
nxt.w=cur.w+dw[i];
if(nxt.x<=0||nxt.x>m||nxt.y<=0||nxt.y>m)continue;//保证在棋盘范围内
nxt.c=a[nxt.x][nxt.y];
if(!nxt.c)continue;
if(cur.c!=nxt.c)nxt.w++;//确定下一步的信息
if(dis[nxt.x][nxt.y]>nxt.w){
dis[nxt.x][nxt.y]=nxt.w;
q.push(nxt);
}
}
}
}
int main(){
int x,y,c;
read(m);read(n);
for(int i=1;i<=n;i++){
read(x);read(y);read(c);
a[x][y]=c+1;
}//这里c+1，为了方便区分无色格子
bfs();
if(!a[m][m]){//处理(m,m)无色情况
int ans=min(dis[m][m-1],dis[m-1][m])+2;
if(ans>=inf)puts("-1");
else printf("%d\n",ans);
}
else{
if(dis[m][m]==inf)puts("-1");
else printf("%d\n",dis[m][m]);
}
return 0;
}
2.最短路（ Dijkstra ）
注：下面的参考程序使用 zkw线段树 代替优先队列，
zkw线段树 短小精悍，常数较小，并且支持直接单点修改，
不需要优先队列的懒惰删除法。
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define maxm 2000005
#define inf 0x3f3f3f3f
template <typename Tp>
void read(Tp &x){
char c=getchar();x=0;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;
}//快速读入，不解释
struct Edge{
int f,t,w,nxt;
}edge[maxm];
int head[maxn],etot=1;//这里有一个小技巧，存图时边数初值设为一个奇数
void add_edge(int f,int t,int w){//这样可以利用位运算成对变化找到反向边
edge[++etot]=(Edge){f,t,w,head[f]};
head[f]=etot;
}//链式前向星存图
//--------以下内容为 zkw线段树
//主要思路，用线段树维护dis
//dis1数组表示在线段树中的dis
//tr数组记录当前最小dis对应的节点编号
//有关zkw线段树，可以参考洛谷日报的讲解，这里不多说
int tr[maxn<<2],dis1[maxn<<2],bt;
int n,m,S,T;
void build(){
for(bt=1;bt<=n+1;bt<<=1);//bt初始化，zkw线段树的初始操作
for(int i=1;i<=n;i++)tr[i+bt]=i;//tr数组初始化
memset(dis1,0x3f,sizeof(dis1));//dis1数组初始化
//因为这里dis初值都是inf，所以可以这样直接赋值
}
void modify(int x,int val){
dis1[x]=val;x+=bt;//单点修改
for(x>>=1;x;x>>=1){//以下是zkw线段树常规操作
if(dis1[tr[x<<1]]<dis1[tr[(x<<1)|1]])tr[x]=tr[x<<1];
else tr[x]=tr[(x<<1)|1];
}
}//其实上面的内容并不是很长，只是注释比较多
int dis[maxn];
void dijkstra(){
memset(dis,0x3f,sizeof(dis));
build();//build()不可忘
dis[S]=0;modify(S,0);//源点更新
int x,y,w;
for(int j=1;j<=n;j++){//这里tr[1]维护的是[1,n]dis的最小值的节点编号，所以直接调用
x=tr[1];modify(x,inf);//这里将x设为极大值，来取代删除操作
for(int i=head[x];i;i=edge[i].nxt){
y=edge[i].t;w=edge[i].w;
if(dis[y]>dis[x]+w){//dijkstra松弛操作
dis[y]=dis[x]+w;
modify(y,dis[y]);//直接更新
}
}
}
}
int dx[]={0,1,0,-1,1,1,-1,-1,0,2,0,-2};//12方向及魔法代价
int dy[]={1,0,-1,0,1,-1,1,-1,2,0,-2,0};
int dw[]={0,0,0,0,2,2,2,2,2,2,2,2};
int a[105][105],cnt[105][105];
struct node{
int x,y,c;
}b[maxn];
//a存储棋盘上格子的颜色
//cnt表示棋盘上的格子对应的节点编号
void preprocess(){//建图
int x,y,c,xx,yy,ww;
for(int i=1;i<=n;i++){
x=b[i].x;y=b[i].y;c=b[i].c;
for(int j=0;j<12;j++){
xx=x+dx[j];yy=y+dy[j];ww=dw[j];
if(a[xx][yy]){
if(a[xx][yy]!=c)ww++;
add_edge(i,cnt[xx][yy],ww);
}
}
}//这一段在上文题解中讲的比较详细，这里不再多说
S=cnt[1][1];
}
int main(){
int mm,x,y,c;
read(mm);read(n);
for(int i=1;i<=n;i++){
read(x);read(y);read(c);
a[x][y]=c+1;cnt[x][y]=i;
b[i]=(node){x,y,c+1};
}//这里c+1，为了方便区分无色格子
preprocess();
dijkstra();//因为在图论中m常代表的含义是边数
if(!a[mm][mm]){//所以用mm取代原题目中的m，即棋盘大小
int ans=min(dis[cnt[mm][mm-1]],dis[cnt[mm-1][mm]])+2;
if(ans>=inf)puts("-1");
else printf("%d\n",ans);
}//(m,m)没有颜色的特判
else{
if(dis[cnt[mm][mm]]==inf)puts("-1");
else printf("%d\n",dis[cnt[mm][mm]]);
}
return 0;
}
记忆化搜索
P3953 [NOIP2017 提高组] 逛公园
ACWing-527. 逛公园
秦大佬题解
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;//数据范围
const int inf=1e9;//最大值
int t,n,m,k,p,ans,flag,vis[N],dis[N],dp[N][55],vis_dp[N][55],x,y,z;//变量
struct node//最近get到的结构体内置,好好玩啊.模板标记
{
int cnt,edge[N<<1],ver[N<<1],Next[N<<1],head[N];//记得边要乘以2,因为要建立反向图
void init()//初始化
{
cnt=0;
memset(head,0,sizeof(head));
}
void add_edge(int x,int y,int z)//建图
{
edge[++cnt]=y;
ver[cnt]=z;
Next[cnt]=head[x];
head[x]=cnt;
}
void spfa(int s)//SPFA,NOIP是不会卡掉我们的.
{
int i,x;
queue<int>q;
for(i=1; i<=n; i++)
{
vis[i]=0;
dis[i]=inf;
}
q.push(s),vis[s]=1,dis[s]=0;
while(q.size())
{
x=q.front();
q.pop();
vis[x]=0;//出来了
for(i=head[x]; i; i=Next[i])//遍历所有的出边
{
int y=edge[i],z=ver[i];
if(dis[x]+z<dis[y])
{
dis[y]=dis[x]+z;//更新
if(vis[y]==0)
{
q.push(y);
vis[y]=1;//标记
}
}
}
}
}
} g1,g2;
void clear()
{
ans=0;
flag=1;
g1.init();//初始化很重要
g2.init();
memset(dp,-1,sizeof(dp));
}
int dfs(int x,int k)
{
int i,j;
if(~dp[x][k])//记忆化搜索
return dp[x][k];
vis_dp[x][k]=1;//标记进入了最短路径
dp[x][k]=0;
for(i=g2.head[x]; i; i=g2.Next[i])
{
int y=g2.edge[i],z=k+dis[x]-(dis[y]+g2.ver[i]);
if(z>=0)//如果是在指定偏差区间内的
{
if(vis_dp[y][z])//之前已经进入过最短路径了,那么显然是无解了.
flag=0;
dp[x][k]+=dfs(y,z);//统计
dp[x][k]%=p;//取得取模
}
}
vis_dp[x][k]=0;//已经从最短路径中出来了.
return dp[x][k];//该返回了
}
int main()
{
scanf("%d",&t);
while(t--)
{
clear();
scanf("%d%d%d%d",&n,&m,&k,&p);
for(int i=1; i<=m; i++)
{
scanf("%d%d%d",&x,&y,&z);
g1.add_edge(x,y,z);
g2.add_edge(y,x,z);//不是无向边,是建立反向图
}
g1.spfa(1);
dp[1][0]=1;
for(int i=0; i<=k; i++)
{
ans+=dfs(n,i);//每一个有冤枉路的路径都要加入
ans%=p;//取模快乐
}
dfs(n,k+1);//再来一下判断
if(!flag)//无解了
puts("-1");
else
printf("%lld\n",ans);
}
return 0;
}
