题解 P1073 【最优贸易】

· · 题解

两遍类spfa，认真来讲应该不算，第一遍正着建图然后得出minn[]，minn[i]表示到i点最小的价格，第二遍逆着建图得出maxx[]，maxx[i]表示从i可以走到n路途中最大的价格，max(minn[i]-maxx[i])即为答案。

代码如下

···cpp

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int q[100005],minn[100002],maxx[100002],num,a[100002],m,n,x,y,z;
int to[500002],pre[500005],to1[500005],pre1[500005],las[100005],las1[100005];
bool vis[100005];
void add(int a,int b)
{
    to[++num]=b;
    pre[num]=las[a];
    las[a]=num;
    to1[num]=a;
    pre1[num]=las1[b];
    las1[b]=num;
}
void spfa()//正着
{
    q[1]=1;
    int qh=0,qt=1,hh=0,tt=0;
    vis[1]=true;
    while((hh*100001+qh)<(tt*100001+qt))//这里大概是个假的循环队列，节约空间
    {
        qh++;
        if(qh>100001)qh=1,hh++;
        int v=q[qh];
        int p=las[v];
        vis[v]=false;
        while(p)
        {
            if(minn[v]<minn[to[p]]||minn[to[p]]>a[to[p]])
            {
                minn[to[p]]=min(minn[v],a[to[p]]);
                if(!vis[to[p]]){
                    if(qt+1>100001)qt=0,tt++;
                    q[++qt]=to[p];
                    vis[to[p]]=true;
                }
            }
            p=pre[p];
        }
    }
}
void spfa1()//逆着
{
    memset(q,0,sizeof(q));
    memset(vis,false,sizeof(vis));
    int qh=0,qt=1,hh=0,tt=0;
    vis[n]=true;q[1]=n;
    while((hh*100001+qh)<(tt*100001+qt))
    {
        qh++;
        if(qh>100001)qh=1,hh++;
        int v=q[qh];
        int p=las1[v];
        vis[v]=false;
        while(p)
        {
            if(maxx[v]>maxx[to1[p]]||maxx[to1[p]]<a[to1[p]])
            {
                maxx[to1[p]]=max(maxx[v],a[to1[p]]);
                if(!vis[to[p]])
                {
                    if(qt+1>100001)qt=0,tt++;
                    q[++qt]=to1[p];
                    vis[to1[p]]=true;
                }
            }
            p=pre1[p];
        }
    }
}
int main()
{
    memset(minn,63,sizeof(minn));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y);
        if(z==2)add(y,x);
    }
    spfa();spfa1();
    int ans=0;
    minn[1]=a[1];maxx[n]=a[n];
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,maxx[i]-minn[i]);
    }
    cout<<ans;
}

···