题解 P2349 【金字塔】
chichichichi
·
·
题解
在机房昏昏欲睡，随手点了下随机跳题看看会有什么神奇黑题，于是就有了这篇题解。
第一眼感觉题目非常眼熟，在看到如此之小的数据范围和蓝题标签，当场瞳孔地震，实在是水。
题解正式开始
并不会高大上的 A^*，将此题模型作为最短路变形来求解的。
如果准备好了以上食材，就接着往下看吧。
设没有打开宝箱时 1到 n 的一条路径 T_i 的长度（用时）为 d_i 。
而有浓烟出现后的最短路径长度为：S=min{ d_i+w_j } ，其中 w_j 是路径 T_i 上一条边的长度。
最坏情况指逃出时间最长，所以 w_j 应该是 路径 T_i 中最长的一条边。
那么有浓烟时，在最坏的情况下所用的时间最少的路径长度应为 S=min{d_i+w_{i_{max}} }
答案就应该为一条【最长边的长度尽量小】的最短路的长度。
最大值最小这个经典问题自然用二分答案来求解。二分路径中最长边的大小，来跑最短路，所有大于二分值的边都不经过。如果当前二分值能够更新答案，说明可能存在更短的边再次更新答案，就让 r=mid，反之就让 l=mid+1。
若有多条起点为 $1$ ，终点为 $n$ 的**最短路径**，长度为 $D$ , 其中第 $i $ 条路径中最长的一条边长度为 $w_i$，我们应该选择 min {$\,w_i\,$}所在的那条路径，否则总存在一个 $w_i$ 使得 $w_i+D<res$ 。
------------
**before the code**
本题解代码只是为了便于理解，有一些地方的实现可能与题解并不相同 ~~（因为我懒得改了）~~
在代码中进行了必要的注释，如果有疑惑欢迎私信或评论。
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int maxn=110;
const int maxm=4001;
int n,m,tot,maxx,res=0x3f3f3f3f;
int lin[maxn],to[maxm],ne[maxm];
int va[maxm],from[maxm];
void add(int u,int v,int k)
{//存图
to[++tot]=v;
ne[tot]=lin[u];
lin[u]=tot;
va[tot]=k;
from[tot]=u;
}
bool check(int w)
{
int vis[maxn],dis[maxn],max1=0;
int pre[maxn];
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[1]=0;
pre[1]=0;
queue<int>q;
vis[1]=1;
q.push(1);//SPFA的准备工作
while(!q.empty())
{
int x=q.front();
q.pop();
vis[x]=0;
for(int i=lin[x];i;i=ne[i])
{
int t=to[i];
if(va[i]<=w)//最长边不大于二分值
{
if(dis[t]>dis[x]+va[i])
{
pre[t]=i;
dis[t]=dis[x]+va[i];
if(!vis[t])
q.push(t);
}
}
}
}
if(dis[n]<=res)//可以更新答案
{
for(int i=pre[n];i;i=pre[from[i]])//找到最长边
{
max1=max(max1,va[i]);
}
res=dis[n]+max1;//更新答案
return 1;
}
return 0;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
maxx=max(maxx,c);
}
//二分最长边的边权
int l=1,r=maxx+10;//配合二分写法，将值域进行扩大
while(l<r)
{
int mid=(l+r)>>1;//注意这种取法mid取不到r
if(check(mid))//可以更新答案
r=mid;
else//不可以更新答案
l=mid+1;
}
printf("%d",res);//输出结果
return 0;
}
```
### **See Ya！**