Luogu

算法

我们要找到一条从$1$到$n$的路径,使得路径上有两个点$p$、$q$(先经过$p$再经过$q$),满足$q$的权值与$p$的权值的差最大。

显然我们要最小化$p$的权值,最大化$q$的权值。

考虑从节点1开始跑Dijkstra,但是将$dis[i]$设为从1到$i$的路径上权值最小的点的权值。

更新方式改为用$min(dis[u],price[v])$来更新$dis[v]$即可。

同样的,再建反图,从节点$n$开始跑,但是将$fdis[i]$设为从$n$到$i$的路径上权值最大的点的权值。

更新方式同理。

最后答案即为$\operatorname{max}\limits_{i=1}^n fdis[i]-dis[i]$。

注意判无法到达的情况,此时不要计入答案。

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int n,m;
int price[100010];

struct Edge { int v,nxt; };
Edge e[1000010],fe[1000010];
int head[100010],fhead[100010];
int cnt=0,fcnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
inline void faddEdge(int u,int v) {
    fe[++fcnt].v=u;
    fe[fcnt].nxt=fhead[v];
    fhead[v]=fcnt;
}

struct Heapnode {
    int u,d;
    bool operator <(const Heapnode& rhs) const {
        return d>rhs.d;
    }
};

int dis[100010],fdis[100010];

inline void Dijkstra() {
    priority_queue<Heapnode> Q;
    memset(dis,0x3f,sizeof(dis));
    dis[1]=price[1]; Q.push((Heapnode){1,dis[1]});
    while (!Q.empty()) {
        Heapnode fr=Q.top(); Q.pop();
        int u=fr.u,d=fr.d;
        if (d!=dis[u]) continue;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v;
            if (min(dis[u],price[v])<dis[v]) {
                dis[v]=min(dis[u],price[v]);
                Q.push((Heapnode){v,dis[v]});
            }
        }
    }
}
inline void fDijkstra() {
    priority_queue<Heapnode> Q;
    memset(fdis,0x3f,sizeof(fdis));
    fdis[n]=price[n]; Q.push((Heapnode){n,fdis[n]});
    while (!Q.empty()) {
        Heapnode fr=Q.top(); Q.pop();
        int u=fr.u,d=fr.d;
        if (d!=fdis[u]) continue;
        for (re int i=fhead[u];i;i=fe[i].nxt) {
            int v=fe[i].v;
            if (max(fdis[u],price[v])<fdis[v]) {
                fdis[v]=max(fdis[u],price[v]);
                Q.push((Heapnode){v,fdis[v]});
            }
        }
    }
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;i++) price[i]=read();
    for (re int i=1;i<=m;i++) {
        int x=read(),y=read(),z=read();
        addEdge(x,y); faddEdge(x,y);
        if (z==2) { addEdge(y,x); faddEdge(y,x); }
    }
    Dijkstra(); fDijkstra();
    int ans=0;
    for (re int i=1;i<=n;i++) {
        if (dis[i]==dis[0]||fdis[i]==fdis[0]) continue;
        ans=max(ans,fdis[i]-dis[i]);
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 18 PM