最优贸易

洛咕

题意:给定n个点m条边(有些单向,有些双向)的图,每个节点都有一个权值\(w[i]\),找出一条从1到n的路径,使得路径上能够找出两个点\(p,q\)(先经过p再经过q),并且"节点q的权值减去节点p的权值"最大.

分析:在正向图上从1开始跑\(spfa\),求出\(dis1[i]\)表示从节点1到节点i的所有路径中,能够经过的权值最小的点.在反向图上从n开始跑\(spfa\),求出\(dis2[i]\)表示从节点n到节点i的左右路径中,能够经过的权值最大的点.然后枚举所有节点i,找到最大的\(dis2[i]-dis1[i]\)即可.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=100005;
const int M=1000005;
int n,m,ans,w[N],dis1[N],dis2[N],visit[N];
int tot1,head1[N],nxt1[M],to1[M];
int tot2,head2[N],nxt2[M],to2[M];
inline void add1(int a,int b){nxt1[++tot1]=head1[a];head1[a]=tot1;to1[tot1]=b;}
inline void add2(int a,int b){nxt2[++tot2]=head2[a];head2[a]=tot2;to2[tot2]=b;}
inline void spfa1(){
    memset(visit,0,sizeof(visit));
    memset(dis1,0x3f,sizeof(dis1));dis1[1]=w[1];
    queue<int>q1;q1.push(1);visit[1]=0;
    while(q1.size()){
        int u=q1.front();q1.pop();visit[u]=0;
        for(int i=head1[u];i;i=nxt1[i]){
            int v=to1[i];
            if(dis1[v]>min(dis1[u],w[v])){
                dis1[v]=min(dis1[u],w[v]);
                if(!visit[v]){q1.push(v);visit[v]=1;}
            }
        }
    }
}
inline void spfa2(){
    memset(visit,0,sizeof(visit));
    memset(dis2,0,sizeof(dis2));dis2[n]=w[n];
    queue<int>q2;q2.push(n);visit[n]=0;
    while(q2.size()){
        int u=q2.front();q2.pop();visit[u]=0;
        for(int i=head2[u];i;i=nxt2[i]){
            int v=to2[i];
            if(dis2[v]<max(dis2[u],w[v])){
                dis2[v]=max(dis2[u],w[v]);
                if(!visit[v]){q2.push(v);visit[v]=1;}
            }
        }
    }
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;++i)w[i]=read();
    for(int i=1;i<=m;++i){
        int a=read(),b=read(),c=read();
        if(c==1)add1(a,b),add2(b,a);
        else{
            add1(a,b);add1(b,a);
            add2(a,b);add2(b,a);
        }
    }
    spfa1();spfa2();
    for(int i=1;i<=n;++i)ans=max(ans,dis2[i]-dis1[i]);
    printf("%d\n",ans);
    return 0;
}