题解 P1073 【最优贸易】

神之右大臣 · 2019-08-21 15:59:45 · 题解

大家都是两遍SPFA吗(或是tarjan)？我这里就是一遍dp啊；

首先判断对于一个点u，是否可以从一号点走到这里，并且可以从u走到n号点； 对于这样的点我们打上标记；

那么抛出水晶球的点一定是从打上标记的点中选出一个；(自己可以理解一下)

然后跑一遍dp，dp[i]表示从点1到点i的若干条路径中，所经过的点的权值最小的值；

比较明显的发现dp[v]可以从dp[u]继承过来(v是u的儿子),所以具有优美的DP性质；

最后ans=max(w[i]-dp[i]);

dp可以通过bfs来实现；

#include <bits/stdc++.h>
#define cin std::ios::sync_with_stdio(false); cin
#define cout std::ios::sync_with_stdio(false); cout
using namespace std;
int n,m;
struct littlestar{
    int to;
    int nxt;
}star[1000010],star2[1000010];
int head[1000010],cnt,head2[1000010],cnt2;
inline void add(int u,int v)
{
    star[++cnt].to=v;
    star[cnt].nxt=head[u];
    head[u]=cnt;
}
inline void add2(int u,int v)
{
    star2[++cnt].to=v;
    star2[cnt].nxt=head2[u];
    head2[u]=cnt;
}
int w[1000010];
queue<int> q;
int bo1[1000010],bo2[1000010];
void bfs1(int s)
{
    while(q.size()) q.pop();
    q.push(s);
    bo1[s]=1;
    while(q.size()){
        int u=q.front();
        q.pop();
        for(register int i=head[u];i;i=star[i].nxt){
            int v=star[i].to;
            if(!bo1[v]){
                bo1[v]=1;
                q.push(v);
            }
        }
    }
}
void bfs2(int s)
{
    while(q.size()) q.pop();
    q.push(s);
    bo2[s]=1;
    while(q.size()){
        int u=q.front();
        q.pop();
        for(register int i=head2[u];i;i=star2[i].nxt){
            int v=star2[i].to;
            if(!bo2[v]){
                bo2[v]=1;
                q.push(v);
            }
        }
    }
}
int f[1000010];
int vis[1000010];
void SPFA()
{
    while(q.size()) q.pop();
    for(register int i=1;i<=n;i++) f[i]=999999999;
    q.push(1);
    f[1]=w[1];
    vis[1]=1;
    while(q.size()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(register int i=head[u];i;i=star[i].nxt){
            int v=star[i].to;
            if(!vis[v]){
                vis[v]=1;
                if(f[v]==999999999){
                    f[v]=min(f[u],w[v]);
                    q.push(v);
                }
                else{
                    if(f[u]<f[v]){
                        f[v]=f[u];
                        q.push(v);
                    }
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(register int i=1;i<=n;i++){
        cin>>w[i];
    }
    for(register int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        if(w==1){
            add(u,v);
            add2(v,u);
        }
        else{
            add(u,v);
            add2(v,u);
            add(v,u);
            add2(u,v);      
        }
    }
    bfs1(1);
    bfs2(n);
    SPFA();
    int ans=0;
    for(register int i=1;i<=n;i++){
        if(bo1[i]&&bo2[i]){
            ans=max(w[i]-f[i],ans);
        }
    }
    cout<<ans<<endl;
}