P1073 最优贸易

songhn · 2018-04-30 23:48:05 · 题解

似乎题解里都是两遍spfa，加堆优化的dijkstra也能过，这道题其实求出两个点a b要b-a最大，而且b的遍历顺序要在a后面，可以考虑两次dijkstra来维护d与v两数组处理，d表示走到这个节点前面能买到的最便宜的货，f表示这个节点往后走最大可以卖出多少钱，当然这算是广义的dijkstra，其实是用它来维护一个动态规划\begin{cases}d[v]=min(d[u],w[v])\\f[v]=max(f[u],w[v])\end{cases} d在正向图跑，同时建一个反向边图跑f，这样就可以保证a点一定在b之前，这样对于一个每点算出f[i]-d[i]后取最大值即可

#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
typedef pair<int,int> p;
int head1[maxn],num1=0,num2=0,head2[maxn];
int n,m,wi[maxn];
int f[maxn],d[maxn];
int vis[maxn];
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')t=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*t;
}
struct node{
    int v,w,nex;
}e1[maxn],e2[maxn];
void add1(int u,int v,int w)
{
    e1[++num1].v=v;
    e1[num1].w=wi[v];
    e1[num1].nex=head1[u];
    head1[u]=num1;
}
void add2(int u,int v,int w)
{
    e2[++num2].v=v;
    e2[num2].w=wi[v];
    e2[num2].nex=head2[u];
    head2[u]=num2;
}
void dij1()
{
    memset(d,0x3f,sizeof(d));
    memset(vis,0,sizeof(vis));
    priority_queue<p,vector<p>,greater<p> > q1;
    d[1]=wi[1];
    q1.push(make_pair(wi[1],1));
    while(!q1.empty())
    {
        int u=q1.top().second;
        q1.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head1[u];i;i=e1[i].nex)
        {
            int v=e1[i].v;
            d[v]=min(d[u],wi[v]);
            q1.push(make_pair(d[v],v));
        }
    }
}
void dij2()
{
    memset(f,-0x3f,sizeof(f));
    memset(vis,0,sizeof(vis));
    priority_queue<p,vector<p>,greater<p> > q2;
    f[n]=wi[n];
    q2.push(make_pair(wi[n],n));
    while(!q2.empty())
    {
        int u=q2.top().second;
        q2.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head2[u];i;i=e2[i].nex)
        {
            int v=e2[i].v;
            f[v]=max(f[u],wi[v]);
            q2.push(make_pair(f[v],v));
        }
    }
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++) wi[i]=read();
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        x=read(),y=read(),z=read();
        if(z==1) add1(x,y,z),add2(y,x,z);
        else add1(x,y,z),add1(y,x,z),add2(x,y,z),add2(y,x,z);
    }
    dij1();
    dij2();
    int ans=0;
    for(int i=1;i<=n;i++) ans=max(ans,f[i]-d[i]);
    printf("%d\n",ans);
    return 0;
}