题解 | #[NOIP2009]最优贸易#

Ciallo～(∠・ω< )⌒☆,大家好，蒟蒻斗胆写的一篇题解，有错误请多多包涵。本题可采用堆优化版本的dijstra算法，dist[i]表示1~i当前的最大价格差，sb[i]表示当前城市水晶石的价格，每次遇到更大的价格差的更新一遍，最后要注意对答案取绝对值，详情请见代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
typedef pair<int,int> pii;

const int N=1e5+10,M=5e5+10;

int n,m;
int st[N];
int dist[N],sb[N];//dist表示i前差价的最大值，对应数的最小值，sb为i城市物品价格
int h[N],e[M],nex[M],idx;

struct node
{
    int cot,x;
    bool operator<(const node &w)const//差价为负数，按照差价的大小从小到大排序
    {
        return w.cot<cot;
    }
};

void add(int a,int b)
{
    e[idx]=b,nex[idx]=h[a],h[a]=idx++;
}

void dijstra()
{
    memset(dist,0x3f,sizeof dist);
    priority_queue<node>p;
    p.push({0,1});
    
    while(!p.empty())
    {
        auto pos=p.top();
        p.pop();
        
        int t=pos.x,sub=pos.cot;
        if(st[t])continue;
        st[t]=1;
        
        for(int i=h[t];i!=-1;i=nex[i])
        {
            int j=e[i];
            //当前差价更小时更新一遍
            if(dist[j]>min(sb[t]-sb[j],sub))
            {
                dist[j]=min(sb[t]-sb[j],sub);
                if(st[j])st[j]=0;//这样处理可以处理双向边的差价
                p.push({dist[j],j});
            }
            
        }
    }
    
}
int main()
{
    int n,m;
    cin>>n>>m;
    
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)cin>>sb[i];
    
    while(m--)
    {
        int a,b,z;
        cin>>a>>b>>z;
        
        add(a,b);
        if(z==2)add(b,a);
    }
    
    dijstra();
    
    if(dist[n]==0x3f3f3f3f)cout<<0<<endl;
    else cout<<abs(dist[n])<<endl;//差价可能为负数，取绝对值
    
}