P14226 最短路好题

· · 题解

P14226 [ICPC 2024 Kunming I] 冲向黄金城。

提供一个不用数据结构的做法。

题目大意：给定一张无向图，边有颜色和边权，有 k 次操作，每次只走颜色为 a_i 的边并且走过的边总权值不超过 b_i，求所有操作后哪些点是可达的。

先考虑一个比较有道理的做法：由于操作有先后顺序，每一次操作都建立在先前操作的基础上，所以考虑独立地审视每个操作。对于操作 i（即第 i 张车票），我们取出颜色为 a_i 的边形成一张新图，以当前的可达点为源点跑 Dijkstra，将最短路长度不超过 b_i 的点设为新的可达点。

为了防止复杂度爆炸，我们选取源点、清空数组时均只考虑与颜色为 a_i 的边有关的点。提供一个非正解代码：

::::info[Code]

#include <bits/stdc++.h>
using namespace std;
#define gc getchar()
#define pb push_back
typedef long long ll;
const int N=5e5+5;
ll rd() {
    ll x=0,f=1; char c=gc;
    for(;c<'0'||c>'9';c=gc) if(c=='-') f=-1;
    for(;c>='0'&&c<='9';x=x*10+c-'0',c=gc);
    return x*f;
}
ll T,n,m,k,dis[N];
bool arr[N],vis[N];
set<int> S;
struct Edge {int u,v; ll w;};
vector<Edge> E[N];
struct node {
    ll pos,val;
    friend bool operator<(node p,node q) {
        return p.val>q.val;
    }
};
vector<node> e[N];
priority_queue<node> pq;
int main() {
    for(T=rd();T;T--) {
        n=rd(); m=rd(); k=rd();
        for(int i=1;i<=n;i++) {arr[i]=vis[i]=0; dis[i]=1e18;}
        for(int i=1;i<=m;i++) E[i].clear();
        for(int i=1,u,v,c,w;i<=m;i++) {
            u=rd(); v=rd(); c=rd(); w=rd();
            E[c].pb({u,v,w});
        }
        arr[1]=1;

        for(int i=1,a,b;i<=k;i++) {
            a=rd(); b=rd();
            for(Edge x:E[a]) {
                int u=x.u,v=x.v,w=x.w;
                if(w>b) continue;
                S.insert(u); S.insert(v);
                e[u].pb({v,w}); e[v].pb({u,w});
            }
            for(set<int>::iterator x=S.begin();x!=S.end();x++)
                if(arr[*x]) {dis[*x]=0; pq.push({*x,0});}
            while(!pq.empty()) {
                int u=pq.top().pos; pq.pop();
                if(vis[u]) continue;
                vis[u]=1;
                for(node x:e[u]) if(dis[x.pos]>dis[u]+x.val && dis[u]+x.val<=b) {
                    dis[x.pos]=dis[u]+x.val;
                    pq.push({x.pos,dis[x.pos]});
                }
            }
            for(set<int>::iterator tmp=S.begin();tmp!=S.end();tmp++) {
                int x=(*tmp);
                if(dis[x]<=b) arr[x]=1;
                dis[x]=1e18; vis[x]=0; e[x].clear();
            }
            S.clear();
        }
        for(int i=1;i<=n;i++) cout<<arr[i]; cout<<'\n';
    }
    return 0;
}

::::

提交代码发现 T 飞了，思考一个极端情况：假如所有的边都是相同的颜色，每次操作的颜色限制也是这个颜色，那么等价于在原图上跑了 k 次 Dijkstra，时间复杂度 O(k(n+m) \log n)，在当前数据范围下无法通过。

虽然这只是一个错解，但是它给我们一个启示：我们要充分利用每次操作求的最短路。

具体的，我们维护 m 个堆，分别储存在通过特定颜色的边的情况下各个点的最短路径长度，每次操作都尝试更新这个堆，当遇到 a_i=c 的操作时，我们直接使用编号为 c 的堆，而不是从零开始建堆。

::::success[AC Code] 以下是正解代码，加入了适量注释。AC Link

#include <bits/stdc++.h>
using namespace std;
#define gc getchar()
#define pb push_back
typedef long long ll;
const int N=5e5+5;
ll rd() {
    ll x=0,f=1; char c=gc;
    for(;c<'0'||c>'9';c=gc) if(c=='-') f=-1;
    for(;c>='0'&&c<='9';x=x*10+c-'0',c=gc);
    return x*f;
}
ll T,n,m,k;
bool vis[N];
set<int> S;
struct Edge {ll to,c,w;};
vector<Edge> e[N];
struct node {
    ll pos,val;
    friend bool operator<(node p,node q) {
        return p.val>q.val;
    }
};
priority_queue<node> pq[N];
int main() {
    for(T=rd();T;T--) {
        n=rd(); m=rd(); k=rd();
        //清空不规范，爆零两行泪！
        for(int i=1;i<=n;i++) vis[i]=0;
        for(int i=1;i<=n;i++) e[i].clear();
        for(int i=1;i<=m;i++) while(!pq[i].empty()) pq[i].pop();
        for(int i=1,u,v,c,w;i<=m;i++) {
            u=rd(); v=rd(); c=rd(); w=rd();
            e[u].pb({v,c,w}); e[v].pb({u,c,w});
        }
        // 1 号点一定是可达的，我们先用这个点更新堆
        for(Edge x:e[1]) pq[x.c].push({x.to,x.w});
        vis[1]=1;
        for(int i=1,a,b;i<=k;i++) {
            a=rd(); b=rd();
            //跑普通 Dijkstra 的同时，把途经点（新的可达点）塞进集合 S 中
            while(!pq[a].empty() && pq[a].top().val<=b) {
                node tmp=pq[a].top(); pq[a].pop();
                ll u=tmp.pos,w=tmp.val;
                if(vis[u]) continue;
                vis[u]=1; S.insert(u);
                for(Edge x:e[u]) if(x.c==a) pq[a].push({x.to,w+x.w});
            }
            //用新增的可达点更新其他颜色的堆
            for(set<int>::iterator it=S.begin();it!=S.end();it++)
                for(Edge x:e[*it]) pq[x.c].push({x.to,x.w});
            S.clear();
        }
        for(int i=1;i<=n;i++) cout<<vis[i];
        cout<<'\n';
    }
    return 0;
}

::::