直接跑的Dij
题目描述
它咕了......
分析
很明显的,如果没有一个斜线连着的两个点,他们之间必须通过一次转换才行,所以可通过这个来建边.
参考代码(手写的堆)
#include<bits/stdc++.h>
using namespace std;
const int N=502,M=510000,T=999999;
char a[N][N];
struct node{
int v,w,nex;
}t[M<<1];
struct thing{
int num,w;
}c[M];
int len,las[M],dis[M],siz;
bool vis[M];
inline void add(int u,int v,int w){
len++;
t[len].v=v,t[len].w=w;
t[len].nex=las[u],las[u]=len;
len++;
t[len].v=u,t[len].w=w;
t[len].nex=las[v],las[v]=len;
}
inline void update(int x){
int fa=x>>1;
if(!fa){
return;
}
if(c[fa].w>c[x].w){
swap(c[fa],c[x]);
update(fa);
return;
}
return;
}
inline void push(int y,int x){
siz++;
c[siz].w=x,c[siz].num=y;
update(siz);
return;
}
inline void down(int x){
int l=x<<1,r=x<<1|1;
if(l>siz){
return;
}
if(r>siz){
if(c[x].w>c[l].w){
swap(c[x],c[l]);
return;
}
return;
}
if(c[l].w>c[r].w){
if(c[x].w>c[r].w){
swap(c[x],c[r]);
down(r);
return;
}
return;
}
if(c[x].w>c[l].w){
swap(c[x],c[l]);
down(l);
return;
}
return;
}
inline void pop(){
swap(c[1],c[siz]);
siz--;
down(1);
return;
}
inline void dij(int goal){
siz=0;
push(1,0);
for(int i=1;i<=goal;++i){
dis[i]=T;
vis[i]=0;
}
dis[1]=0;
while(siz){
thing p=c[1];
pop();
if(vis[p.num]){
continue;
}
vis[p.num]=1;
for(int i=las[p.num];i;i=t[i].nex){
int v=t[i].v,w=t[i].w;
if(dis[v]>dis[p.num]+w){
dis[v]=dis[p.num]+w;
push(v,dis[v]);
}
}
}
if(dis[goal]>=T-1){
printf("NO SOLUTION\n");
return;
}
printf("%d\n",dis[goal]);
}
inline void clear(int goal){
for(int i=1;i<=goal;++i){
las[i]=0;
}
len=0;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,m;
scanf("%d%d",&n,&m);
n++,m++;
for(int i=1;i<n;++i){
for(int j=1;j<m;++j){
scanf(" %c",&a[i][j]);
if(a[i][j]=='/'){
add((i-1)*m+j,i*m+j+1,1);
add((i-1)*m+j+1,i*m+j,0);
continue;
}
add((i-1)*m+j,i*m+j+1,0);
add((i-1)*m+j+1,i*m+j,1);
}
}
dij(n*m);
clear(n*m);
}
return 0;
}
tql
是STL不香了,还是queue不好用了?
您大佬%%%
CSP不找手感?小蒟蒻当然只有这样
%%%