图论最短路之虫洞

题目

思路

这道题很明显是最短路，主要是建边有点困难，这里会用到分层图

#include<bits/stdc++.h>
using namespace std;
const int Size=2000000+100;
int ver[Size],Next[Size],edge[Size],head[Size],w[Size],s[Size];
bool col[Size];
int tot,n,m;
inline void add(int x,int y,int z){
    ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
}
inline int read(){
    int s=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&& ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s;
}
int vis[Size],dis[Size];
queue<int>q;
int spfa(int s,int t){
    if(col[s]==1) s=n+1;
    memset(dis,0x3f,sizeof(dis));
    memset(vis,false,sizeof(vis));
    dis[s]=0,vis[s]=true;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=Next[i]){
            int v=ver[i];
            if(dis[v]>dis[u]+edge[i]){
                dis[v]=dis[u]+edge[i];
                if(vis[v]==0){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }

    }
    return min(dis[t],dis[t+n]);
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) col[i]=read();
    for(int i=1;i<=n;i++) w[i]=read();
    for(int i=1;i<=n;i++){
        s[i]=read();
    }
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),k=read();
        if(col[u]==col[v]){
            add(u,v+n,k);
            add(u+n,v,k);
        }
        else{
            int tmp=abs(w[u]-w[v]);
            add(u+n,v+n,k+tmp);
            add(u,v,max(k-tmp,0));
        }
    }
    for(int i=1;i<=n;i++){
        add(i,i+n,0);
        add(i+n,i,s[i]);
    }
    printf("%dn",spfa(1,n));
    return 0;
}