P1396 营救 题解

本文主要是介绍P1396 营救 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目传送门

分析

这题有好几种方法可以做，有跑最短路的，有些最小生成树的。这里介绍最短路的方法。

单源最短路径，很自然地想到 Dijkstra。不过题目要求的是最大值最小，所以松弛就要改成：

if(dis[v]>max(dis[u],e[i].w))dis[v]=max(dis[u],e[i].w);

代码实现

#include <bits/stdc++.h>
using namespace std;int n,m,s,t;
struct edge{int to,nxt,w;
}e[(int)2e4<<1];
int head[10005],idx;
void link(int x,int y,int w){e[++idx]={y,head[x],w};head[x]=idx;
}
struct poi{int d,p;bool operator<(const poi&x)const{return d>x.d;}
};
priority_queue<poi>q;
int dis[10005];
bool vis[10005];
int main(){cin>>n>>m>>s>>t;for(int i=1,x,y,z;i<=m;i++){cin>>x>>y>>z;link(x,y,z);link(y,x,z);}memset(dis,0x3f3f3f3f,sizeof(dis));dis[s]=0;q.push(poi{0,s});while(!q.empty()){int u=q.top().p;q.pop();if(vis[u])continue;vis[u]=true;for(int i=head[u];i;i=e[i].nxt){int v=e[i].to;if(dis[v]>max(dis[u],e[i].w)){dis[v]=max(dis[u],e[i].w);q.push(poi{dis[v],v});}}}cout<<dis[t];return 0;
}

这篇关于P1396 营救 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---