社区讨论

为什么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 条回复,欢迎继续交流。

正在加载回复...