网站建设织梦怎么样,wordpress做图片集,南京网站建设咨询,外包公司不给员工发工资怎么办题目链接#xff1a;[NOIP2009 提高组] 最优贸易 - 洛谷 思路#xff1a;这道题的标签是SPFA#xff0c;但是我觉得这道题可以用记忆化搜索#xff0c;用两组dfs#xff0c;将从1到 i点道路上的最小值都存进min数组#xff0c;将i 到n点的最大值存进max组#xff0c;最后… 题目链接[NOIP2009 提高组] 最优贸易 - 洛谷 思路这道题的标签是SPFA但是我觉得这道题可以用记忆化搜索用两组dfs将从1到 i点道路上的最小值都存进min数组将i 到n点的最大值存进max组最后遍历min与max两数组的最大差值输出即可。其中借助vector容器将每个点连通的点都遍历到。
AC代码
#includebits/stdc.h
using namespace std;
vectorintway_min[110000];
vectorintway_max[110000];
int value[110000],minn[110000],maxx[110000];
void dfs_min(int x,int m)
{ if(mminn[x])return ;mmin(m,value[x]);minn[x]m;for(int i0;iway_min[x].size();i){dfs_min(way_min[x][i],m);}
}
void dfs_max(int x,int m)
{if(mmaxx[x])return ;mmax(m,value[x]);maxx[x]m;for(int i0;iway_max[x].size();i){dfs_max(way_max[x][i],m);}
}
int main()
{int n,m,x,y,z,ans0;cinnm;for(int i1;in;i){cinvalue[i];minn[i]1000;maxx[i]-1000;}for(int i1;im;i){cinxyz;way_min[x].push_back(y);way_max[y].push_back(x);if(z2){way_min[y].push_back(x);way_max[x].push_back(y);}}dfs_min(1,value[1]);dfs_max(n,value[n]);for(int i1;in;i)ansmax(ans,maxx[i]-minn[i]);coutansendl;return 0;
}
