题目链接
看题解后感觉分层图好像非常NB巧妙
建三层n个点的图，每层图对应的边相连，权值为0
即从一个城市到另一个城市，不进行交易的收益为0
第一层的点连向第二层对应的点的边权为-w[i],表示买入的收益
第二层的点连向第三层对应的点的边权为w[i],表示卖出的收益
这样跑一遍最长路，就可以了
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
#define N 300030
#define M 1200030
int n,m,dis[N],tot,Head[N];
queue<int> q;
bool inque[N];
struct NODE{
int to,next,w;
} e[M];
inline int read(){
int x=; char c=getchar();
while(c<''||c>'') c=getchar();
while(''<=c&&c<='') { x=(x<<)+(x<<)+c-''; c=getchar(); }
return x;
}
inline void add(int x,int y,int w){
e[++tot].to=y;
e[tot].w=w;
e[tot].next=Head[x];
Head[x]=tot;
}
inline void unionn(int x,int y){
add(x,y,);
add(x+n,y+n,);
add(x+n+n,y+n+n,);
}
int main()
{
n=read(); m=read();
int x,y,z;
for(int i=;i<=n;i++){
x=read();
add(i,i+n,-x);
add(i+n,i+n+n,x);
}
add(n,n+n+n+,);
for(int i=;i<=m;i++){
x=read(); y=read(); z=read();
unionn(x,y);
if(z==) unionn(y,x);
}
add(n+n+n,n+n+n+,);
memset(dis,-,sizeof(dis));
q.push(); dis[]=;
while(!q.empty()){
int u=q.front(); q.pop();
inque[u]=;
for(int i=Head[u];i;i=e[i].next){
int v=e[i].to;
if(dis[v]<dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
if(!inque[v]){
inque[v]=;
q.push(v);
}
}
}
}
printf("%d\n",dis[n+n+n+]);
return ;
}
