洛谷P1073最优贸易—

题目：https://www.luogu.org/problemnew/show/P1073

由于任何城市都可以多次经过，所以可以随便走，也就不用太在意有向边和无向边，把无向边当做两条有向边处理；

根据题意，价格较小的城市要先于价格较大的城市被经过，然而它又可以随便走，所以不妨分开考虑；

每个点维护两个值，一个是从起点到它的最小值，一个是从终点到它的最大值，在每个城市的二者之差中取MAX即可；

于是问题转化为求两个单源最短路，对于终点出发的那个，将边全部反向进行最短路即可。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

priority_queue< pair<int,int> >q;

int const MAXN=1e5+,MAXM=5e5+;

int n,m,head[MAXN],ct,s[MAXN],t[MAXN],head2[MAXN],ct2,cost[MAXN],ans;

bool vis[MAXN];

struct N{

    int to,next;

    N(int t=,int n=):to(t),next(n) {}

}edge[MAXM],edge2[MAXM];

void add(int x,int y,int z)

{

    edge[++ct]=N(y,head[x]);head[x]=ct;

    edge2[++ct2]=N(x,head2[y]);head2[y]=ct;

    if(z==)

    {

        edge[++ct]=N(x,head[y]);head[y]=ct;

        edge2[++ct2]=N(y,head2[x]);head2[x]=ct;

    }

}

void dijkstra1()

{

    while(q.size())q.pop();

    memset(s,0x3f,sizeof s);

    memset(vis,,sizeof vis);

    s[]=cost[];q.push(make_pair(-cost[],));//大根堆

    while(q.size())

    {

        int x=q.top().second;q.pop();

        if(vis[x])continue;//!

        vis[x]=;

        for(int i=head[x],u;i;i=edge[i].next)

            if(s[u=edge[i].to]>min(s[x],cost[u]))

            {

                s[u]=min(s[x],cost[u]);

                q.push(make_pair(-s[u],u));

            }

    }

}

void dijkstra2()

{

    while(q.size())q.pop();

    memset(t,-,sizeof t);

    memset(vis,,sizeof vis);

    t[n]=cost[n];q.push(make_pair(cost[n],n));//大根堆

    while(q.size())

    {

        int x=q.top().second;q.pop();

        if(vis[x])continue;//!

        vis[x]=;

        for(int i=head2[x],u;i;i=edge2[i].next)

            if(t[u=edge2[i].to]<max(t[x],cost[u]))

            {

                t[u]=max(t[x],cost[u]);

                q.push(make_pair(t[u],u));

            }

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

        scanf("%d",&cost[i]);

    for(int i=,x,y,z;i<=m;i++)

    {

        scanf("%d%d%d",&x,&y,&z);

        add(x,y,z);

    }

    dijkstra1();

    dijkstra2();

    for(int i=;i<=n;i++)

        ans=max(ans,t[i]-s[i]);

    printf("%d",ans);

    return ;

}

巴特西

洛谷P1073最优贸易——双向取值

最新文章

热门文章