题解 P2296 【寻找道路】

· · 题解

这题超级锻炼思维的！最好是能自己想一想做出来！

如果你实在不会分析，我就来说说我做这道题是怎么从10分到AC想的吧(:з」∠)

对于题目的两个要求我们可以做如下分析：

这句话乍一看不好理解，但是观察样例解释我们可以发现，这个限制的实质就是：删除不与终点连通的点，以及与他们连一条边的点。

  1. 删除这个操作我们常用打标记的方法，在枚举图的时候遇到没打标记的点就跳过即可。
  2. 删除不与终点连通的点，用通俗的话讲就是你倒着从终点出发，把图搜完都到不了的点。倒着从终点出发可以直接反向存边，暴力搜索，给搜索到的点打上标记即可
  3. 对于没搜到的点，如何删去他们连边的点呢？依然用暴力的想法（O(10000）复杂度），枚举所有没打标记的点，枚举他们的连边消去他们的标记不就好了吗？

至此，第一个要求便分析完毕，但是有一个细节要注意：

不能直接消去第一次打上的标记！！你在第二次删除标记时是可能有后效性的，即删去一个与不与终点连接的点后，下一次搜到那个点他还会做一遍删除操作，即把相隔两条边的点给去掉了，与题不符！！

于是重新备份一下标记，用那个备份标记判断即可。感谢大佬提醒

这个很好理解，跳过没有标记的点跑一边最短路即可。因为你一开始存边是倒着存的，其实你不必重新存一遍，直接从终点出发，找到起点的最短路即可。两者应该是等价的。(:з」∠)

最后上我丑陋的代码：

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
struct ed{
    int u;
    int nex;
}e[300000];
int n,m,x,y,d[300000],fir[20000],st,s,t;
bool v[20000],ok[20000],vis[20000];
void add(int u,int v)
{
    e[++st].u=u; e[st].nex=fir[v]; fir[v]=st;
}

void spfa(int b)  //最短路 
{
    memset(v,0,sizeof(v));
    memset(d,0x3f3f,sizeof(d));
    queue<int> q; q.push(b); v[b]=1; d[b]=0;
    while (!q.empty())
    {
        int k=q.front(); q.pop(); v[b]=0;
        for (int i=fir[k];i;i=e[i].nex)
        {
            int u=e[i].u,w=1;
            if (d[u]>d[k]+w&&ok[e[i].u]) {
                d[u]=d[k]+w;
                if (!v[u]) v[u]=1,q.push(u);
            }   
        }
    }
}

void bfs(int t)  //第一次的搜边 
{
    memset(v,0,sizeof(v));
    queue<int> q; q.push(t); ok[t]=v[t]=1;
    while (!q.empty())
    {
        int k=q.front(); q.pop();
        for (int i=fir[k];i;i=e[i].nex)
        if (!v[e[i].u]){
            int u=e[i].u; if (!v[u]) v[u]=1,ok[u]=1,q.push(u);
        }
    }
}
int main()
{
    cin>>n>>m;
    for (int i=1;i<=m;i++) cin>>x>>y,add(x,y);
    cin>>s>>t; 
    bfs(t);
    for (int i=1;i<=n;i++) vis[i]=ok[i];
    for (int i=1;i<=n;i++) 
    if (!vis[i]) for (int j=fir[i];j;j=e[j].nex){
    if (ok[e[j].u]) ok[e[j].u]=0; 
    // 不能直接修改，有后效性。 
    }
    spfa(t);
    if (d[s]>=(0x3f3f)) cout<<"-1"<<endl;
    else cout<<d[s]<<endl;
    retrun 0;
}

各位把关键部分看看就好，如代码有错误那一定是我故意的(:з」∠)