P1811

模拟赛读错题了，读错后的题意就是这道题，写完后发现没有相同思路的，所以写篇题解纪念一下。

由于是无权最短路，所以考虑 bfs，但是只用 bfs 我们无法判定这样走能否满足限制。

于是考虑升维，我们设

dis_{u,v}

表示最后经过了

v\to u

这条边时

u

的最短路，这样就非常好转移了，对于另一条边

u \to w

，有

dis_{w,u} \gets dis_{u,v}+1

，这表示我们走了

v \to u

这条边后又走了

u \to w

这条边，发现这样就可以做了，我们只需要判一下有没有

(v,u,w)

这个三元组，如果有就不能转移。

发现这样做有

O\left( \sum^n_{i=1} deg_{i} \right)

个点，和

O\left( \sum^n_{i=1} deg_{i}^2 \right)

次转移，第一项就是

O(m)

，第二项在是菊花图的时候会被卡成

O(m^2)

，虽然仍能过本题，但我们肯定希望能做到

m=10^6

级别，考虑继续优化。

我们发现，bfs 时有非常多相同的转移，比如在

K=0

时所有

dis_{u}

都相同。我们肯定希望

dis_{u,v}

在有值了后不再访问

dis_{u,v}

，考虑怎么去掉。这个其实是简单的，我们可以在更新

dis_{u,v}

后直接删除

v\to u

这条边。这样除了收到限制的情况，每条边只会被访问一次。而限制只有

K

个，所以总共会访问

O(m+K)

次边，总时间复杂度也是

O(m+K)

的。

不过我的实现中用了 map 所以实际会多一个

\log

。另外输出路经我们记录一下每种情况从哪里转移来的就行

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f,MOD=1e9+7;
#define iosize 1048576
char *p1,*p2,buf[iosize];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,iosize,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
    int x=0,f=1;
    char ch=nc();
    while(ch<48||ch>57)
    {
        if(ch=='-')
            f=-1;
        ch=nc();
    }
    while(ch>=48&&ch<=57)
        x=x*10+ch-48,ch=nc();
    return x*f;
}

const int N=5e5+10;
int n,m,q;
int tot;
int head[N];
struct edge{int v,nxt;}e[4*N];
void add(int u,int v)
{
    tot++;
    e[tot]={v,head[u]};
    head[u]=tot;
}
map<int,int> pre[N];
map<int,int> dis[N];
map<pair<int,pair<int,int> > ,bool> mp;
void bfs(int u,int fa)
{
    queue<pair<int,int> > q;
    dis[u][fa]=1;
    q.push(make_pair(u,fa));
    while(q.size())
    {
        int u=q.front().first;
        int fa=q.front().second;
        q.pop();
        for(int lst=0,i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            int t=lst;
            lst=i;
            if(mp.count(make_pair(fa,make_pair(u,v)))) continue;
            if(t==0) head[u]=e[i].nxt;//用链式前向星删掉这条边
            else e[t].nxt=e[i].nxt;
            lst=t;
            if(dis[v].count(u)) continue;
            pre[v][u]=fa;
            dis[v][u]=dis[u][fa]+1;
            q.push(make_pair(v,u));
        }
    }
}
signed main() 
{    
    n=read(),m=read(),q=read();
    for(int i=1;i<=m;i++)
    {
        int u,v;
        u=read(),v=read();
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=q;i++)
    {
        int u,v,w;
        u=read(),v=read(),w=read();
        mp[make_pair(u,make_pair(v,w))]=true;
    }
    bfs(1,0);
    int ans=INF;
    int res=0;
    for(auto e:dis[n])
    {
        if(e.second<ans) ans=e.second,res=e.first;
    }
    cout<<ans-1<<endl;
    vector<int> Ans;
    int now=n;
    int t=res;
    while(now)
    {
        Ans.push_back(now);
        int x=t;
        t=pre[now][t];
        now=x;
    }
    for(int i=Ans.size()-1;i>=0;i--) cout<<Ans[i]<<" ";
    return 0;
}

文章操作

相关推荐

评论

P1811