题解：P15716 [JAG 2023 Summer Camp #2] Drifting

· · 题解

分析

要求最短路，首先我们注意到这是一个 DAG，然后我们自然想到类似拓扑地解决。由于整张图只有一个转移方向，所以我们直接 DP，等到一个点所有边都被松弛了再让它加到队列中，每条边只会被松弛一次，所以时间复杂度是正确的。

实现有比较多的细节。（当然也有可能是我写得比较丑，具体看代码）

代码

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <cstring>
#define getchar getchar_unlocked
#define N 200005
#define ll long long
using namespace std;
int n,mm,u,v,w,h[N],t,k,cnt,in[N]; 
vector<int> b,c[N],y;
map<pair<int,int>,int> m;
struct Ed{
    int v,nxt,w;
};
Ed e[N<<1];
inline void add(int u,int v,int w){
    e[++t]=Ed{v,h[u],w};
    h[u]=t;
}
struct ha{
    int u,v;
    ll w;
    inline bool operator < (const ha &o) const{
        return w<o.w;
    }
};
vector<ha> d[N];
queue<ha> q;
inline void topo(){
    for(int i=1;i<=n;i++) if(!in[i]) q.push({0,i,0});
    q.pop();
    while(!q.empty()){
        ha u=q.front();
        q.pop();
        for(int i=h[u.v];~i;i=e[i].nxt){
            in[e[i].v]--;
            if(!in[e[i].v]) q.push({0,e[i].v,0});
        }
    } //将除 1 之外的入度为 0 的边先把点的入度减去，因为无贡献
    q.push({0,1,0});
    b.push_back(1);
    while(1){
        while(!q.empty()){
            ha u=q.front();q.pop(); 
            d[u.v].push_back({u.u,u.v,u.w});
        }
        if(b.empty()) break;
        for(int u:b){ 
            sort(d[u].begin(),d[u].end());
            for(int i=h[u];~i;i=e[i].nxt) if(!(--in[e[i].v])) y.push_back(e[i].v);//将入度删到 0 的边准备入队
            for(ha x:d[u]) if(~h[u]){
                int *pre=&h[u];
                bool fl=m.count({x.u,x.v});
                int p;
                if(fl) p=m[{x.u,x.v}];
                for(int i=h[u];~i;i=e[i].nxt){
                    if(fl&&binary_search(c[p].begin(),c[p].end(),e[i].v)){
                        *pre=i;
                        pre=&e[i].nxt;
                    }//链式前向星，用链表快速删边
                    else q.push({u,e[i].v,x.w+e[i].w}); 
                } 
                *pre=-1;
            }
        }
        b.clear();
        swap(b,y);
    } 
}
inline void read(int &x){
    x=0;
    char ch=getchar();
    while(ch>57||ch<48) ch=getchar();
    while(ch>=48&&ch<=57){
        x=x*10+(ch^48);
        ch=getchar();
    }
} 
int main(){
    memset(h,-1,sizeof(h));
    read(n),read(mm);
    for(int i=1;i<=mm;i++){
        read(u),read(v),read(w);
        add(u,v,w);
        in[v]++;
    } 
    read(k);
    for(int i=1;i<=k;i++){
        read(u),read(v),read(w);
        if(!m.count({u,v})) m[{u,v}]=++cnt;
        c[m[{u,v}]].push_back(w);//处理边
    } 
    for(int i=1;i<=cnt;i++) sort(c[i].begin(),c[i].end());
    topo();
    sort(d[n].begin(),d[n].end());
    if(d[n].empty()) puts("-1");
    else printf("%lld",d[n][0].w); 
    return 0;
}