书画网站模板下载,久久建筑网免费下载,WordPress购物个人中心,山东企业网站建设推荐前言
这道题感谢朋友的帮助#xff0c;这里是他的博客地址#xff1a; http://blog.csdn.net/sugar_free_mint 题目
一个无向图#xff0c;每个点和边都有一定的权值#xff0c;要求从点1到点2在经过边的权值小于b的情况下经过点的最大权值尽量小
输入
4 4 8(4个点,4条…前言
这道题感谢朋友的帮助这里是他的博客地址 http://blog.csdn.net/sugar_free_mint 题目
一个无向图每个点和边都有一定的权值要求从点1到点2在经过边的权值小于b的情况下经过点的最大权值尽量小
输入
4 4 8(4个点,4条边,要求边的权值小于8) 8(第一个点的权值) 5 6 10 2 1 2(2到1有条边权值为2) 2 4 1 1 3 4 3 4 3
输出
10 解题思路
先看看能否到达不然输出AFK。然后如果可以用二分法找最优答案 代码
#includecstdio
#includecstring
#includeiostream
using namespace std;
struct woc{int w,x,y,next;
};//邻接表
woc a[100001];
int n,m,b,xx,yy,ww,ls[10001],head,tail,cost[10001],t,state[10001];
bool v[10001];
long long f[10001];
bool spfa(int money)//如果经过点权值小于money是否可以到达
{memset(f,127/3,sizeof(f));//初始化if (cost[1]money) return false;//没用head0;tail1;v[1]true;state[1]1;f[1]0;//初始化while (head!tail){head;//入队head(head-1)%n1;//循环队列tls[state[head]];//联通该点的一条边while (t!0){if (f[a[t].x]a[t].wf[a[t].y]){f[a[t].y]f[a[t].x]a[t].w;if (!v[a[t].y] cost[a[t].y]money)//看看点是否满足要求{tail;//入队tail(tail-1)%n1;//循环队列state[tail]a[t].y;v[a[t].y]true;//标记}}ta[t].next;//下一条边}v[state[head]]false;//解封}if (f[n]b) return true;return false;//返回结果
}
int main()
{int u0,mid,l,r;scanf(%d%d%d,n,m,b);for (int i1;in;i){scanf(%d,cost[i]);rmax(r,cost[i]);}lmax(cost[1],cost[n]);for (int i1;im;i){scanf(%d%d%d,xx,yy,ww);a[u].xxx;a[u].yyy;a[u].www;a[u].nextls[xx];ls[xx]u;a[u].yxx;a[u].xyy;a[u].www;a[u].nextls[yy];ls[yy]u;//无向图}if (!spfa(1000000001)) {printf(AFK);return 0;}//是否可以到达while (lr){mid(lr)/2;//二分if (spfa(mid)) rmid-1;else lmid1;}printf(%d,l);//输出
}
