答案6但是输出5
by Addrian @ 2023-11-03 14:38:13
bfs是什么鬼，SPFA不好吗
by R_aier @ 2023-11-03 14:53:12
```cpp
对每个点
addedge(i,i+n,-v);
addedge(i+n,i+n*2,v);
对每条边
add(u,v);
add(u+n,v+n);
add(u+n*2,v+n*2);
if(w==2) {add(v,u),
add(v+n,u+n),
add(v+n*2,u+n*2);}
```
然后SPFA最长路
by R_aier @ 2023-11-03 14:59:33
已经改好了
大概是没有反着再求一遍
```
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
const int N=1e5+5;
const int M=1e6+5;
int d[N*3];
queue<int> q;
int n,m;
int z[N];
vector<int> son[3*N];
bool cf1[3*N];
bool cf2[3*N];
void add(int x,int y){
son[x].push_back(y);
return ;
}
void bfs(int cs){
q.push(cs);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=0;i<son[x].size();i++){
int y=son[x][i];
if(y<=n){
d[y]=max(d[x],d[y]);
}else if(y>n&&y<=2*n){
d[y]=d[y-n]+z[y-n];
d[y]=max(d[x],d[y]);
d[y+n]=d[y];
}else{
d[y]=max(d[x],d[y]);
}
if(cs==1||cs==n+1||cs==n*2+1){
if(cf1[y]==1)continue;
cf1[y]=1;
}else{
if(cf2[y]==1)continue;
cf2[y]=1;
}
q.push(y);
}
}
return ;
}
int x,y,pd;
int main(){
cin>>n>>m;
for(int i=1;i<=3*n;i++){
d[i]=-200;
}
for(int i=1;i<=n;i++){
cin>>z[i];
d[i]=-1*z[i];
}
for(int i=1;i<=m;i++){
cin>>x>>y>>pd;
add(x,y);
add(x+n,y+n);
add(x+2*n,y+2*n);
if(pd==2){
add(y,x);
add(y+n,x+n);
add(y+2*n,x+2*n);
}
}
bfs(1);
bfs(n);
bfs(1+n);
bfs(2*n);
bfs(1+n*2);
bfs(3*n);
cout<<d[3*n];
return 0;
}
```
本帖结
by Addrian @ 2023-11-03 15:24:52
@[R_aier](/user/891245)
我并不会，嗯我去学一下
就是用了一个神奇的分层图（我也不知道算不算）然后就成了一个神奇的做法
谢谢您，抱歉我太废了
by Addrian @ 2023-11-03 15:27:07
我丢，我只是写了个什么抽象玩意
by Addrian @ 2023-11-03 16:39:54