导视设计网站,申请域名有什么用,菜谱网站模版,网站开发哪家好正题
luogu评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP3831 题目大意
有n∗nn*nn∗n的铁路网走一格代价为2#xff0c;mmm个中转站可以改变方向代价为1。求两个点之间的最短路。 解题思路
我们发现n∗nn*nn∗n很大#xff0c;所以我们考虑根据mmm…正题
luogu评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP3831 题目大意
有n∗nn*nn∗n的铁路网走一格代价为2mmm个中转站可以改变方向代价为1。求两个点之间的最短路。 解题思路
我们发现n∗nn*nn∗n很大所以我们考虑根据mmm建图。算上起点和终点为中转站。
对于每个中转站我们只连接上下左右最近的点这个排序可以做到。这样边数就不会太多。可是如何解决转向的问题。
对于每个点拆成横点和纵点横着的连横点竖着的连纵点横点和纵点之间建立一条边长度为1。
问题完美解决 codecodecode
#includecstdio
#includevector
#includealgorithm
#includequeue
#includecstring
#define py(aaa) aaa*2-1
#define px(aaa) aaa*2
using namespace std;
const int N200100,L20010;
struct node{int to,next,w;
}a[N*5];
vectorint in_x[L],in_y[L];
queueint q;
int ls[N],tot,n,m,f[N],v[N],x[N],y[N];
bool cmp_x(int xs,int ys)
{return y[xs]y[ys];}
bool cmp_y(int xs,int ys)
{return x[xs]x[ys];}
void addl(int x,int y,int w)
{a[tot].toy;a[tot].ww;a[tot].nextls[x];ls[x]tot;
}
int spfa(int s,int t)
{memset(f,0x3f,sizeof(f));f[py(s)]f[px(s)]0;q.push(py(s));q.push(px(s));while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(f[x]a[i].wf[y]){f[y]f[x]a[i].w;if(!v[y]){q.push(y);v[y]true;}}}v[x]false;}if(f[px(t)]1061109567) return -1;return min(f[px(t)],f[py(t)]);
}
int main()
{scanf(%d%d,n,m);m2;for(int i1;im;i){scanf(%d%d,x[i],y[i]);in_x[x[i]].push_back(i);in_y[y[i]].push_back(i);addl(px(i),py(i),1);addl(py(i),px(i),1);}for(int i1;in;i)sort(in_x[i].begin(),in_x[i].end(),cmp_x);for(int k1;kn;k)for(int i0;i1in_x[k].size();i){int asin_x[k][i],bsin_x[k][i1];addl(px(as),px(bs),(y[bs]-y[as])*2);addl(px(bs),px(as),(y[bs]-y[as])*2);}for(int i1;in;i)sort(in_y[i].begin(),in_y[i].end(),cmp_y);for(int k1;kn;k)for(int i0;i1in_y[k].size();i){int asin_y[k][i],bsin_y[k][i1];addl(py(as),py(bs),(x[bs]-x[as])*2);addl(py(bs),py(as),(x[bs]-x[as])*2);}printf(%d,spfa(m-1,m));
}
