P2349 金字塔 题解

p2349
思绪

SPFA，最短路。这题要在路径上最大值双倍的情况下，求出最短路。我们可以再盘算每一步的时间算出当前路径的最大值。
假设当前位置是now，下一步是v，边权是w。那么有两种情况

•                                    v                         .                         m                         a                         x                         >                         w                              v.max > w                  v.max>w
  
•                                    v                         .                         m                         a                         x                         ≤                         w                              v.max \leq w                  v.max≤w。
  如果是第一种情况，那么当前路径的最大值不消变，直接加上w即可。
                                      d                         i                         s                         [                         v                         ]                         .                         s                         u                         m                         =                         d                         i                         s                         [                         n                         o                         w                         ]                         .                         s                         u                         m                         +                         w                              dis[v].sum=dis[now].sum+w                  dis[v].sum=dis[now].sum+w
  如果是第二种情况，分析最大值须要更新，那么须要把先前所双倍盘算的最大值减去，也是就减去v.max,固然还要加上双倍的w。
                                      d                         i                         s                         [                         v                         ]                         .                         s                         u                         m                         =                         d                         i                         s                         [                         n                         o                         w                         ]                         .                         s                         u                         m                         +                         w                         +                         w                         −                         d                         i                         s                         [                         n                         o                         w                         ]                         .                         m                         a                         x                         x                              dis[v].sum=dis[now].sum+w+w-dis[now].maxx                  dis[v].sum=dis[now].sum+w+w−dis[now].maxx
  留意更新max的时间，不可以在当前的最大值与w之间取最大值。由于max取的是当前路径的最大值，而不是以当前点作为尽头的全部路上的最大值。
  

留意
代码

1. #include<bits/stdc++.h>
2. #include<cstring>
3. #include<queue>
4. #include<set>
5. #include<stack>
6. #include<vector>
7. #include<map>
8. #define ll long long
9. #define lhs printf("\n");
10. using namespace std;
11. const int N=1e5+10;
12. const int M=2024;
13. const int inf=0x3f3f3f3f;
14. int n,m;
15. vector<int> a[N];
16. vector<int> b[N];
17. struct node
18. {
19.         int sum,maxx;
20. }dis[N];
21. void spfa()
22. {
23.         for(int i=1;i<=N;i++)
24.         {
25.                 dis[i].maxx=0;
26.                 dis[i].sum=inf;
27.         }
28.         queue<int> q;
29.         q.push(1);
30.         dis[1].sum=0;
31.         while(q.size())
32.         {
33.                 int now=q.front();
34.                 q.pop();
35.                 for(int i=0;i<a[now].size();i++)
36.                 {
37.                         int v=a[now][i];
38.                         int w=b[now][i];       
39.                         if(w>dis[now].maxx)
40.                         {
41.                                 if(dis[v].sum>dis[now].sum+w+w-dis[now].maxx)
42.                                 {
43.                                         dis[v].sum=dis[now].sum+w+w-dis[now].maxx;
44.                                         dis[v].maxx=w;
45.                                         q.push(v);
46.                                 }
47.                         }
48.                         else
49.                         {
50.                                 if(dis[v].sum>dis[now].sum+w)
51.                                 {
52.                                         dis[v].maxx=dis[now].maxx;
53.                                         dis[v].sum=dis[now].sum+w;
54.                                         q.push(v);
55.                                 }
56.                         }
57.                 }
58.         }
59. }
60. int main()
61. {
62.         scanf("%d%d",&n,&m);
63.         for(int i=1;i<=m;i++)
64.         {
65.                 int x,y,z;
66.                 scanf("%d%d%d",&x,&y,&z);
67.                 a[x].push_back(y);
68.                 b[x].push_back(z);
69.                 a[y].push_back(x);
70.                 b[y].push_back(z);
71.         }
72.         spfa();
73.         printf("%d\n",dis[n].sum);
74. //        for(int i=1;i<=n;i++)
75. //        {
76. //                cout<<dis[i].sum<<" "<<dis[i].maxx<<"\n";
77. //        }
78.         return 0;
79. }
80. /*
81. 7 8
82. 1 2 114
83. 2 3 200
84. 1 3 100
85. 3 4 5
86. 4 6 10
87. 4 5 20
88. 5 7 30
89. 4 7 40
90. */

复制代码

AC纪录

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金