AcWing 4240. 青蛙（最短路 or 最小生成树）

题目连接

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

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

思路 思路一（最短路）

我们直接跑一个最短路就好，基本上所有的最短路都可以，然后注意的是我们在做松弛操作的时候，也就是判断是否应该加入我们的优先队列中的时候，我们做的不是一个加上这条边而是和这条边去一个max，也就是如果我们当前正在对起点t，终点j做一个松弛操作，那么我们做的不是dis[j]=max(dis[j],dis[t]+w)而是dis[j]=max(dis[t],w)我们这样就能记录下最长边了，那么现在的dis[i]表示的就是从1开始到i结束的最长边的长度，而不是累计长度

思路二（最小生成树）

其实你发现没有，我们这里要求的问题其实就是让这个图联通的最大长度，那么这不就是最小生成树吗，我们对边进行排序，排完序后我们开始将边不断地加入集合中，最后让这个图联通的这个边自然就是整个连通图的最长距离了，所以我们可以直接通过最小生成树来解决这个问题

代码 最短路代码

#include
using namespace std;

#define ll long long
#define PII pair
const int N = 2e2+10;

int dis[N],n;

struct Point{
	int x,y;
}V[N];

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

bool vis[N];

void DJ(){
	priority_queue que;
	que.push({0,1});
	dis[1] = 0;
	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  max(dis[t],k)){
				dis[j] = max(dis[t],k);
				que.push({dis[j],j});
			}
		}
	}
}

inline int get_len(Point a,Point b){
	return (a.x-b.x) * (a.x-b.x) + (a.y-b.y) * (a.y-b.y);
}

void init(){
	for(int i = 1;i >n,n){
		init();
		for(int i = 1;i >V[i].x>>V[i].y;
		for(int i = 1;i