@[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