洛谷上能想到分层图psfa解的真是天才

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 100005
int n,m,mny[MAXN],dis[MAXN*3]; 
struct edge
{
    int u,v;
};
vector<edge> g[MAXN*3];
void psfa()
{
    queue<int> q;
    bool visited[MAXN*3];
    memset(visited,0,sizeof visited);
    for(int i=1;i<=n*3;i++) dis[i]=INT_MIN;
    dis[1]=0,visited[1]=1;q.push(1);
    while(!q.empty())
    {
        int k=q.front();q.pop();
        visited[k]=0;
        for (int i=0;i<g[k].size();i++)
        {
            edge Nowp=g[k][i];
            if (dis[Nowp.u]<dis[k]+Nowp.v)
            {
                dis[Nowp.u]=dis[k]+Nowp.v;
                if (!visited[Nowp.u]) visited[Nowp.u]=1,q.push(Nowp.u);
            }
        }
    } 
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        cin>>mny[i];
        g[i].push_back({i+n,-mny[i]});
        g[i+n].push_back({i+2*n,mny[i]});
    } 
    for (int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,0}),g[u+n].push_back({v+n,0}),g[u+2*n].push_back({v+2*n,0});
        if (w==2)  g[v].push_back({u,0}),g[v+n].push_back({u+n,0}),g[v+2*n].push_back({u+2*n,0});
    }
    psfa();
    cout<<dis[n*3];
    return 0;
}