从算法题理解Spfa算法与Dijsktra算法本质区别

#include<iostream>
using namespace std;
#include<cstring>
#include<queue>
 
typedef pair<int,int> PII;
 
const int N = 1e5+10, M = 2e6+10, INF = 0x3f3f3f3f;
int hs[N],e[M],ne[M],w[M],idx;
int price[N],ht[N],n,m,dmax[N],dmin[N];
bool st[N];
 
void add(int h[],int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
 
//flag为真表示求正向走路买入的最小值
void SPFA(int u,int h[],int dist[],bool flag){
    memset(st,0,sizeof(st));
    queue<int>q;
    if(flag) memset(dist,0x3f,sizeof(dmax));
    dist[u]=price[u];
    q.push(u);
    st[u]=true;
    
    while(q.size()){
        int t=q.front();
        q.pop();
        //每次出队后设置为未访问，保证后面距离能继续更新
        st[t]=false;
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if((flag&&dist[j]>min(price[j],dist[t]))||(!flag&&dist[j]<max(dist[t],price[j]))) {
                if(flag) dist[j]=min(price[j],dist[t]);
                else dist[j]=max(dist[t],price[j]);
                if(!st[j]){
                    st[j]=true;
                    q.push(j);
                }
            }
        }
    }
}
 
int main(){
    cin>>n>>m;
    
    for(int i=1;i<=n;i++) scanf("%d",&price[i]);
    
    memset(hs,-1,sizeof(hs));
    memset(ht,-1,sizeof(ht));
    
    int a,b,c;
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&a,&b,&c);
//建立反向图
        add(hs,a,b),add(ht,b,a);
        if(c==2) add(hs,b,a),add(ht,a,b);
    }
    
//这里求最小值从1开始，求最大值从n开始
//因为结合路程图，我们是在1~i城市买入水晶球，在i~n城市卖出水晶球
//所以要从1开始求到达i之前买入水晶球最少价格
//从n开始求到达i之前能够卖出的最大价格，之后做差值
    SPFA(1,hs,dmin,true);
    SPFA(n,ht,dmax,false);
    
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,dmax[i]-dmin[i]);
    
    cout<<res<<endl;
    
    return 0;
}