欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【luogu1462】通往奥格瑞玛的道路 [最短路][spfa]

程序员文章站 2022-07-13 11:58:03
...

 luoguP1462 通往奥格瑞玛的道路 

我的心路历程:有城市中最多的一次收取的费用的最小值 你要说什么???你在问什么??? 【luogu1462】通往奥格瑞玛的道路 [最短路][spfa]

然后看到一个语文课代表的理解:经过城市最多的一次 这次的费用最小值是多少 这不是二分????嘿嘿嘿这几天还在练

结果【luogu1462】通往奥格瑞玛的道路 [最短路][spfa]【luogu1462】通往奥格瑞玛的道路 [最短路][spfa]

感谢csy 和我一起经历了这段玄学错误的修改

  • if(!q.empty()&&blood[v]<=blood[q.front()]) q.push_front(v);//要判队列非空 不然会溢出 当场去世
    
  • 然后是道路是双向的 忘了2倍  (我是个弟弟)
  • 最大值开小了 然后开大了又用的memset 溢出....
  • 二分while是(l<=r)
  • 排序要再开一个数组来排

我恨沙雕样例

【luogu1462】通往奥格瑞玛的道路 [最短路][spfa]【luogu1462】通往奥格瑞玛的道路 [最短路][spfa]
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=10000+5,inf=1e9;
 4 int n,m,blo,w[N],ww[N];
 5 inline int rd()
 6 {
 7     int x=0,w=0;char ch=0;
 8     while(!isdigit(ch)) w|=ch=='-',ch=getchar();
 9     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
10     return w?-x:x;
11 }
12 int head[N],cnt=0;
13 struct edge
14 {
15     int v,nxt,sh;
16 }e[N*5*2];
17 void add(int u,int v,int sh)
18 {
19     e[++cnt].v=v;
20     e[cnt].sh=sh;
21     e[cnt].nxt=head[u];
22     head[u]=cnt;
23 }
24 
25 int vis[N],blood[N];
26 bool spfa(int k)
27 {
28     memset(vis,0,sizeof(vis));
29     for(int i=0;i<=n;i++) blood[i]=inf;
30     deque<int> q;
31     q.push_back(1);
32     vis[1]=1,blood[1]=0;
33     while(!q.empty())
34     {
35         int u=q.front();
36         q.pop_front();vis[u]=0;
37         for(int i=head[u];i;i=e[i].nxt)
38         {
39             int v=e[i].v,sh=e[i].sh;
40             if(blood[v]>blood[u]+sh&&w[v]<=k)
41             {
42                 blood[v]=blood[u]+sh;
43                 if(!vis[v])
44                 {
45                     if(!q.empty()&&blood[v]<=blood[q.front()]) q.push_front(v);
46                     else q.push_back(v);
47                     vis[v]=1;    
48                 }
49             }
50         }
51     }
52     if(blood[n]>blo) return 0;
53     else return 1;
54 }
55 
56 int main()
57 {
58     memset(head,0,sizeof(head));
59     n=rd(),m=rd(),blo=rd();
60     for(int i=1;i<=n;i++) w[i]=rd(),ww[i]=w[i];
61     for(int i=1;i<=m;i++)
62     {
63         int u=rd(),v=rd(),sh=rd();
64         add(u,v,sh);add(v,u,sh);
65     }
66     if(!spfa(inf)) printf("AFK");
67     else
68     {
69         int l=1,r=n;
70         sort(ww+1,ww+1+n);//
71         while(l<=r)
72         {
73             int mid=(l+r)>>1;
74             if(spfa(ww[mid])) r=mid-1;
75             else l=mid+1;
76         }
77         printf("%d",ww[l]);
78     }
79     return 0;
80 }
100昏 spfa+二分 SLF优化

【luogu1462】通往奥格瑞玛的道路 [最短路][spfa]