AcWing 4241. 货物运输

题目连接

https://www.acwing.com/problem/content/description/4244/

http://poj.org/problem?id=1797

思路

这题其实和上一个青蛙这题很相似，传送门,我们知道青蛙求得是让1和n连通的最大路径最小，而我们这个货物运输要求的是最小路径最大，不就是反过来了吗，我们只需要将初始状态全部变为 − I N F -INF −INF， d i s [ 0 ] dis[0] dis[0]变为 I N F INF INF，然后我们每次对点做松弛操作的时候其实就是 d i s [ j ] = m a x ( d i s [ j ] , m i n ( d i s [ t ] , k ) ) dis[j]=max(dis[j],min(dis[t],k)) dis[j]=max(dis[j],min(dis[t],k))这里的 j j j表示下一个点， t t t表示当前的点， k k k表示这条边的长度，只要当前的 d i s [ j ] dis[j] dis[j]是小于这个值的那么我们就更新 d i s [ j ] dis[j] dis[j]的值,这样就能让 d i s [ j ] dis[j] dis[j]最小路径最大值

代码

#include
using namespace std;

#define ll long long
#define PII pair
const int N = 1e3+10;

int dis[N],n,m;


struct Node{
	int v,w;
};
vector E[N];

bool vis[N];

void DJ(){
	priority_queue que;//,vector,greater
	que.push({0,1});
	dis[1] = 0x3f3f3f3f;
	while(!que.empty()){
		int w = que.top().first;
		int t = que.top().second;
		que.pop();
		if(vis[t]) continue;
		vis[t] = true;
		for(int i = 0,l = E[t].size(); i n>>m;
		init();
		int u,v,w;
		for(int i = 1;i >u>>v>>w;
			E[u].push_back({v,w});
			E[v].push_back({u,w});
		}
		
		DJ();
		cout