对于测试点2,本蒟蒻发现该点的数据与样例2几乎一模一样,只是调换了添加边的顺序,然鹅窝的程序可过样例2但卡在了测试点2
#include<bits/stdc++.h>
using namespace std;
int n, m, s, t;
const int N=1e4+1;
const int inf=2e5+1;
int dis[N];
bool vis[N], flag[N];
struct edge{
int to, cost;
};
vector<edge> adj[N], ant_adj[N];
struct node{
int num, cost;
bool operator < (const node&a)const{
return cost>a.cost;
}
};
priority_queue<node> q;
void init(bool ide)
{
swap(s, t);
for(int i=1;i<=n;i++)
{
if(ide)
{
vis[i]=false;
if(dis[i]==inf)
flag[i]=true;
}
dis[i]=inf;
if(i==s)
dis[i]=0;
q.push(node{i, dis[i]});
}
return;
}
void Dijkstra()
{
while(!q.empty())
{
node t=q.top();
q.pop();
if(vis[t.num])
continue;
vis[t.num]=true;
for(int i=0;i<ant_adj[t.num].size();i++)
if(dis[ant_adj[t.num][i].to]>dis[t.num]+ant_adj[t.num][i].cost)
{
dis[ant_adj[t.num][i].to]=dis[t.num]+ant_adj[t.num][i].cost;
q.push(node{ant_adj[t.num][i].to, dis[ant_adj[t.num][i].to]});
}
}
}
void Dijkstra_sec()
{
while(!q.empty())
{
node t=q.top();
q.pop();
if(vis[t.num])
continue;
vis[t.num]=true;
for(int i=0;i<adj[t.num].size();i++)
{
if(flag[adj[t.num][i].to])
{
dis[t.num]=inf;
break;
}
if(dis[adj[t.num][i].to]>dis[t.num]+adj[t.num][i].cost)
{
dis[adj[t.num][i].to]=dis[t.num]+adj[t.num][i].cost;
q.push(node{adj[t.num][i].to, dis[adj[t.num][i].to]});
}
}
}
}
int main()
{
cin>>n>>m;
int tx, ty;
for(int i=0;i<m;i++)
{
cin>>tx>>ty;
adj[tx].push_back(edge{ty, 1});
ant_adj[ty].push_back(edge{tx, 1});
}
cin>>s>>t;
init(false);
Dijkstra();
init(true);
Dijkstra_sec();
cout<<(dis[t]==inf?-1:dis[t])<<endl;
return 0;
}
采用了建反图跑Dijkstra的形式检索图中路径上的出边所指向的点不直接或间接与终点连通的点。随后对该点进行标记,设置其dis值为inf(无限大) 码风奇特,小心食用<^.^>