社区讨论
为什么CE???换了c++11就直接AC了
P3831[SHOI2012] 回家的路参与者 4已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @mi6uee2q
- 此快照首次捕获于
- 2025/11/20 10:59 4 个月前
- 此快照最后确认于
- 2025/11/20 10:59 4 个月前
CPP
#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#include<map>
#include<cmath>
using namespace std;
#define getchar() *v++;
#define ri register int
#define ll long long
char Read[(1<<24)+10000],*v=Read;
int n,m,go,x,y,z,u,cnt=1,a1,a2,b1,b2;
int dis[1000005],head[1000005];
struct star{
int next,to,w,x,y;
}e[5000005];
void add1(int u,int v)
{
e[cnt].to=v;e[cnt].next=head[u];
e[cnt].x=u;
e[cnt].y=v-n;
head[u]=cnt++;
}
void add2(int u,int v)
{
e[cnt].to=v;e[cnt].next=head[u];
e[cnt].x=v;
e[cnt].y=u-n;
head[u]=cnt++;
}
inline int read()
{
int num=0,w=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar(); }
while(ch>='0'&&ch<='9') num=(num<<3)+(num<<1)+ch-'0',ch=getchar();
return num*w;
}
inline int min(int a,int b)
{return a>b?b:a;}
struct cmp{
bool operator()(const int& x,const int& y)
{
return dis[x]>dis[y];
}
};
priority_queue<int,vector<int>,cmp>q;
void dijkstra()
{
while(!q.empty())//存边的编号——代表此边起交点
{
int u=q.top();
q.pop();
if(e[u].x==a2||e[u].y==b2)//若本链可达终点
dis[cnt+1]=min(dis[cnt+1],dis[u]+((abs(e[u].x-a2)+abs(e[u].y-b2))<<1));
for(ri i=head[e[u].x];i;i=e[i].next)//选取可达的链
{
if(dis[u]+((abs(e[u].x-e[i].x)+abs(e[u].y-e[i].y))<<1)+1<dis[i])
{
dis[i]=dis[u]+((abs(e[u].x-e[i].x)+abs(e[u].y-e[i].y))<<1)+1;
q.push(i);
}
}
for(ri i=head[e[u].y+n];i;i=e[i].next)//选取可达的链
{
if(dis[u]+((abs(e[u].x-e[i].x)+abs(e[u].y-e[i].y))<<1)+1<dis[i])
{
dis[i]=dis[u]+((abs(e[u].x-e[i].x)+abs(e[u].y-e[i].y))<<1)+1;
q.push(i);
}
}
}
}
int main()
{
fread(Read,1,1<<24,stdin);
n=read();m=read();int x,y;
for(ri i=1;i<=m;++i)
{
x=read();y=read();
add1(x,y+n);add2(y+n,x);
}
a1=read();b1=read();a2=read();b2=read();
for(ri i=1;i<=cnt+1;++i)
dis[i]=2147483647;
for(ri i=1;i<=(m<<1);++i)//改边的终点
if(e[i].x==a1||e[i].y==b1) dis[i]=((abs(e[i].x-a1)+abs(e[i].y-b1))<<1)+1,q.push(i);
dijkstra();
printf("%d",dis[cnt+1]);
return 0;
}
回复
共 6 条回复,欢迎继续交流。
正在加载回复...