luoguP1462 通往奥格瑞玛的道路 https://www.luogu.org/problemnew/show/P1462
我的心路历程: 有城市中最多的一次收取的费用的最小值 你要说什么??? 你在问什么???
然后看到一个语文课代表的理解: 经过城市最多的一次 这次的费用最小值是多少 这不是二分?? 嘿嘿嘿这几天还在练
结果
感谢 csy 和我一起经历了这段玄学错误的修改
if(!q.empty()&&blood[v]<=blood[q.front()]) q.push_front(v);// 要判队列非空 不然会溢出 当场去世
然后是道路是双向的 忘了 2 倍 (我是个弟弟)
最大值开小了 然后开大了又用的 memset 溢出....
二分 while 是 (l<=r)
排序要再开一个数组来排
我恨沙雕样例
- #include<bits/stdc++.h>
- using namespace std;
- const int N=10000+5,inf=1e9;
- int n,m,blo,w[N],ww[N];
- inline int rd()
- {
- int x=0,w=0;char ch=0;
- while(!isdigit(ch)) w|=ch=='-',ch=getchar();
- while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
- return w?-x:x;
- }
- int head[N],cnt=0;
- struct edge
- {
- int v,nxt,sh;
- }e[N*5*2];
- void add(int u,int v,int sh)
- {
- e[++cnt].v=v;
- e[cnt].sh=sh;
- e[cnt].nxt=head[u];
- head[u]=cnt;
- }
- int vis[N],blood[N];
- bool spfa(int k)
- {
- memset(vis,0,sizeof(vis));
- for(int i=0;i<=n;i++) blood[i]=inf;
- deque<int> q;
- q.push_back(1);
- vis[1]=1,blood[1]=0;
- while(!q.empty())
- {
- int u=q.front();
- q.pop_front();vis[u]=0;
- for(int i=head[u];i;i=e[i].nxt)
- {
- int v=e[i].v,sh=e[i].sh;
- if(blood[v]>blood[u]+sh&&w[v]<=k)
- {
- blood[v]=blood[u]+sh;
- if(!vis[v])
- {
- if(!q.empty()&&blood[v]<=blood[q.front()]) q.push_front(v);
- else q.push_back(v);
- vis[v]=1;
- }
- }
- }
- }
- if(blood[n]>blo) return 0;
- else return 1;
- }
- int main()
- {
- memset(head,0,sizeof(head));
- n=rd(),m=rd(),blo=rd();
- for(int i=1;i<=n;i++) w[i]=rd(),ww[i]=w[i];
- for(int i=1;i<=m;i++)
- {
- int u=rd(),v=rd(),sh=rd();
- add(u,v,sh);add(v,u,sh);
- }
- if(!spfa(inf)) printf("AFK");
- else
- {
- int l=1,r=n;
- sort(ww+1,ww+1+n);//
- while(l<=r)
- {
- int mid=(l+r)>>1;
- if(spfa(ww[mid])) r=mid-1;
- else l=mid+1;
- }
- printf("%d",ww[l]);
- }
- return 0;
- }
100 昏 spfa + 二分 SLF 优化
来源: http://www.bubuko.com/infodetail-2957404.html