求调代码

P2296 [NOIP2014 提高组] 寻找道路

@[PlayerSS](/user/586924) 为什么要处理正反向边,这题不是有向图吗?
by Gokix @ 2022-09-16 17:56:31


@[Gokix](/user/150064) 反向跑出与终点相连的点
by 已注销9bmDsqNdx6GD @ 2022-09-16 20:47:44


Dij 里面 s 和全局起点 s 重名了 但问题不是主要在这里
by Gokix @ 2022-09-16 21:21:03


@[Gokix](/user/150064) 全局和局部重名了应该是以局部优先吧
by 已注销9bmDsqNdx6GD @ 2022-09-16 21:22:09


@[PlayerSS](/user/586924) 没大理解你找与终点相连的点是怎么做的 你 Dij 里有句 `if(u==t)return;` 按照我的理解,你调用 `Dijkstra(1,t);` 时一开始 u 就是 t,也就是你只是把 ok[0][t] 打上标记之后就结束函数了。
by Gokix @ 2022-09-16 21:23:22


@[Gokix](/user/150064) 或许这里还有个错:反向应该跑出所有可以连到终点的点 或许我就应该分开写(
by 已注销9bmDsqNdx6GD @ 2022-09-16 21:33:16


PS:目前代码是这样的 ```cpp #include<bits/stdc++.h> using namespace std; const int N=1e4+10,M=2e5+10; int n,m,s,t,tot=0; int h[N],d[2][N],ok[2][N],vis[N]; struct Node{ int u; int v; int nxt; }e[2][M]; struct node{ int u; int d; bool operator <(const node &a)const{ return d>a.d; } }; void add(int u,int v){ ++tot; e[0][tot]=(Node){u,v,h[u]}; e[1][tot]=(Node){v,u,h[u]}; h[u]=tot; } void Dijkstra(int o,int s,int t){ memset(d[o],0x3f,sizeof(d[o])); memset(vis,false,sizeof(vis)); d[o][s]=0; if(o)ok[1][s]=true; priority_queue<node>q; q.push((node){s,0}); while(!q.empty()){ node p=q.top(); q.pop(); int u=p.u; if(!o&&u==t)return; if(vis[u])continue; vis[u]=true; for(int i=h[u];i>0;i=e[o][i].nxt){ int v=e[o][i].v; if(!o&&!ok[0][v])continue; ok[1][v]=true; if(o){ q.push((node){v}); }else{ if(d[o][u]+1<d[o][v]){ d[o][v]=d[o][u]+1; q.push((node){v,d[o][v]}); } } } } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;++i){ int u,v; scanf("%d%d",&u,&v); if(u==v)continue; add(u,v); } scanf("%d%d",&s,&t); Dijkstra(1,t,s); memcpy(ok[0],ok[1],sizeof(ok[1])); for(int i=1;i<=n;++i){ if(ok[0][i]){ for(int j=h[i];j>0;j=e[0][j].nxt){ int v=e[0][j].v; if(!ok[0][v]){ ok[0][i]=false; break; } } } } Dijkstra(0,s,t); if(d[0][t]>=0x3f3f3f3f){ printf("%d",-1); }else{ printf("%d",d[0][t]); } return 0; } ```
by 已注销9bmDsqNdx6GD @ 2022-09-16 21:45:22


|