暴力+动规
其实能这样做完全是因为只能进行一次贸易,我们就只需要在这个过程中不断更新最大和最小,并把他们赋给相应节点即可.
参考代码
//Kano!!!
//かの!!!
#include<bits/stdc++.h>
using namespace std;
#define INF 0x7f7f7f7f
#define N 100005
vector<int> boy[N];
int n,m,f[N],mi[N],cost[N];
/*
每次要让差值尽量大,
存储当前如果要买一个水晶球的最小值.
每次更新差价.
*/
inline void dfs(int now,int minn,int fa) {
bool flag=1;
minn=min(cost[now],minn);
if(mi[now]>minn){
mi[now]=minn;
flag=0;
}
int maxx=max(f[fa],cost[now]-minn);
if(f[now]<maxx){
f[now]=maxx;
flag=0;
}
if(flag) return;
for (int i=0;i<boy[now].size();i++) dfs(boy[now][i],minn,now);
}
int main() {
scanf("%d%d",&n,&m);
for (int i=0;i<N;i++) mi[i]=INF;
for (int i=1;i<=n;i++) scanf("%d",&cost[i]);
for (int i=1;i<=m;i++) {
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
boy[x].push_back(y);
if (z==2) boy[y].push_back(x);
}
dfs(1,INF,0);
printf("%d\n",f[n]);
return 0;
}
かの,鹿乃?(●ˇ∀ˇ●)
かの,鹿乃?(●ˇ∀ˇ●)
嗯呢