solution

分层图最短路，SPFA

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

const int N = 300010,M = 3000010;

int e[M],ne[M],h[N],w[M],idx;
void add(int a,int b,int c){
    e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx ++;
}

int n,m;
int val[N],dis[N];
bool vis[N];

void init(){
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i = 1;i<=n;i ++){
        cin>>val[i];
    }
    for(int i = 1,u,v,c;i<=m;i ++){
        cin>>u>>v>>c;
        if(c == 1){
            for(int j = 0;j<=2;j ++){
                add(u+j*n,v+j*n,0);
            }
        }
        else{
            for(int j = 0;j<=2;j ++){
                add(u+j*n,v+j*n,0);
                add(v+j*n,u+j*n,0);
            }
        }
    }
    for(int i = 1;i<=n;i ++){
        add(i,n+i,-val[i]);
        add(n+i,n+n+i,val[i]);
    }
    add(n,n+n+n,0);
}

void solve(){
    memset(dis,-0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
    queue<int> q;
    q.push(1);dis[1] = 0;
    vis[1] = true;
    while(q.size()){
        int t = q.front();
        q.pop();
        vis[t] = false;
        for(int i = h[t];~i;i = ne[i]){
            int j = e[i];
            if(dis[j] < dis[t] + w[i]){
                dis[j] = dis[t] + w[i];
                if(!vis[j]){
                q.push(j);
                vis[j] = true;}
            }
        }
    }
    printf("%d\n",dis[n+n+n]);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    init();
    solve();
    return 0;
}