最短路spfa

利用spfa的搜索，暴力更新每一个点的最大差价，和最小成本
对最短路不是很熟悉，开始写的时候把最大差价的初始值赋错了，汗

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=5e5+55;
const int M=1e5+55;
int head[N<<1],val[M];
int cnt;
struct node{
    int to,next;
}mp[N<<1];
struct nod{
    int maxn,minn;
}eg[M];
void add(int x, int y)
{
    mp[cnt].to=y;
    mp[cnt].next=head[x];
    head[x]=cnt++;
}
void Spfa()
{
    bool p[M];
    memset(p,false,sizeof(p));
    queue<int >q;
    q.push(1);
    p[1]=true;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        p[u]=false;
        for(int i=head[u];~i;i=mp[i].next){
            int to=mp[i].to;
            if(eg[to].minn>eg[u].minn){
                eg[to].minn=eg[u].minn;
                if(!p[to]){
                    q.push(to);
                    p[to]=true;
                }
            }
            if(eg[to].maxn<val[to]-eg[to].minn){
                eg[to].maxn=val[to]-eg[to].minn;
                if(!p[to]){
                    q.push(to);
                    p[to]=true;
                }
            }
            if(eg[to].maxn<eg[u].maxn){
                eg[to].maxn=eg[u].maxn;
                if(!p[to]){
                    q.push(to);
                    p[to]=true;
                }
            }
        }
    }
}
int main() {
    int n, m, x, y, k;
    while (~scanf("%d%d", &n, &m)) {
        cnt = 0;
        memset(head, -1, sizeof(head));
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &x);
            eg[i].maxn = -1;                     //要将初始值，赋为大于0的数，不然可能在第一次时不能将数据压入队列；
            eg[i].minn = x;
            val[i] = x;
        }
        for (int i = 0; i < m; ++i) {
            scanf("%d%d%d", &x, &y, &k);
            if (k == 1)
                add(x, y);
            else {
                add(x, y);
                add(y, x);
            }
        }
        Spfa();
        printf("%d\n", eg[n].maxn);
    }
    return 0;
}