问题描述：在一个无向图中，求得一条路径，使得该条路径上的最大值最小

该问题的模板

显然可以用这种最小生成树的做法

但是有这样一种做法：

用状态转移方程：

dp[v]=min(dp[v],max(dp[u],len(u,v)))

其中u,v之间有边

用这个状态转移方程跑dijkstra算法可以求解

类似于这篇题解

求证这种做法对此类问题的正确性

后来我又发现了这种问题的双关键字版本这题

#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<stack>
using namespace std;
const int maxn=1e4+10;
const double eps=1e-6;
struct node{
	int id;
	double d,p;
	node(int id_,double d_,double p_){
		id=id_,d=d_,p=p_;
	}
	node(){}
}tmp,dis[maxn];
struct edge{
	int nxt,to;
	double d,p;
}e[maxn];
bool vis[maxn],g[maxn][maxn];
int n,m,s,t,pre[maxn],head[maxn],cnt=1;
bool operator <(node x,node y){
	if(abs(x.d-y.d)<eps) return x.p>y.p;
	else return x.d>y.d;
}
bool cmp(node x,node y){
	if(abs(x.d-y.d)<eps) return x.p<y.p;
	else return x.d<y.d;	
}
void add(int u,int v,double d,double p){
	e[cnt].d=d,e[cnt].p=p,e[cnt].to=v,e[cnt].nxt=head[u];
	head[u]=cnt++;
}
priority_queue<node>q;
stack<int>sta; 
int main(){
	while(~scanf("%d%d",&n,&m)){ 
		scanf("%d%d",&s,&t);
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=n;i++) dis[i].d=dis[i].p=1.0*0x3f3f3f3f;
		for(int i=1;i<=m;i++){
			int u,v;
			double d,p;
			scanf("%d%d%lf%lf",&u,&v,&d,&p);
			tmp.d=d,tmp.p=p;
			add(u,v,d,p);add(v,u,d,p);
		}
		q.push(node(s,0.0,0.0)),dis[s].d=0.0,dis[s].p=0.0;
		while(!q.empty()){
			node u=q.top();
		//	printf("u=%d\n",u.id);
			q.pop();
			if(vis[u.id]) continue;
			vis[u.id]=1;
			for(int j=head[u.id];j;j=e[j].nxt){
				int i=e[j].to;
			//	printf("v=%d\n",i);
				tmp=node(i,max(dis[u.id].d,e[j].d),dis[u.id].p+e[j].p);
				if(cmp(tmp,dis[i])&&!vis[i]){
					dis[i]=tmp;q.push(tmp);pre[i]=u.id;
				} 
			}
		}
		sta.push(t);
		for(int i=pre[t];i;i=pre[i]) sta.push(i);
		while(!sta.empty()){
			printf("%d ",sta.top());sta.pop();
		}
		printf("\n");
	//	for(int i=1;i<=n;i++) printf("i=%d dis=%lf p=%lf\n",i,dis[i].d,dis[i].p);
		printf("%lf %lf\n",dis[t].d,dis[t].p);
	}
	return 0;
}

于是我用上述做法WA了

用最小生成树的做法可AC

求这题为什么最短路的做法不行

求证明或证伪