@[真姬八彩](/space/show?uid=100439)
写个分层图多好
```
#include <queue>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <algorithm>
#define re register int
#define fr(i,j,k) for(re i=j;i<=k;++i)
using namespace std;
const int N = 300005;
inline int in() {
register int x=0,f=1;
register char ch=getchar();
while(!isdigit(ch)) {
if(ch=='-') f=-f;
ch=getchar();
}
while(isdigit(ch)) {
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
vector<int>v[N],t[N];
queue<int>q;
int n,m,d[N];
bool flag[N];
inline void spfa() {
memset(d,0x3f,sizeof(d));
memset(flag,0,sizeof(flag));
d[1]=0; q.push(1); flag[1]=1;
while(!q.empty()) {
int u=q.front(); q.pop();
int s=t[u].size()-1; flag[u]=0;
fr(i,0,s)
if(d[t[u][i]] > d[u] + v[u][i]) {
d[t[u][i]]=d[u]+v[u][i];
if(!flag[t[u][i]]) {
flag[t[u][i]]=1;
q.push(t[u][i]);
}
}
}
}
int main(void) {
n=in(); m=in();
fr(i,1,n) {
int value;
value=in();
v[i].push_back(value);
t[i].push_back(i+n);
v[i+n].push_back(-value);
t[i+n].push_back(i+n+n);
}
fr(i,1,m) {
int a,b,c;
a=in(); b=in(); c=in();
if(c==1) {
v[a].push_back(0);
t[a].push_back(b);
v[a+n].push_back(0);
t[a+n].push_back(b+n);
v[a+n+n].push_back(0);
t[a+n+n].push_back(b+n+n);
}
else {
v[a].push_back(0);
t[a].push_back(b);
v[a+n].push_back(0);
t[a+n].push_back(b+n);
v[a+n+n].push_back(0);
t[a+n+n].push_back(b+n+n);
v[b].push_back(0);
t[b].push_back(a);
v[b+n].push_back(0);
t[b+n].push_back(a+n);
v[b+n+n].push_back(0);
t[b+n+n].push_back(a+n+n);
}
}
spfa();
printf("%d",max(0,0-d[n+n+n]));
return 0;
}
```
by 静谧时空 @ 2019-08-20 14:18:15