大胆写Dijkstra ！！

· · 题解

看了楼下各位大佬的题解，发现大佬都是用的时间复杂度有点玄学SPFA，所以本蒟蒻就毫不犹豫的写了一个dijkstra+堆优化的程序。

然后看本题，其实个人认为和最短路意义上还是有区别的，因为题目是求可达终点的所有经过路径中最长的一段边权的最小值，所以它不一定要在s到t最短路上。所以裸的最短路板子肯定不行（ 亲测0分 ）

但是

我们仔细思考一下，对于任意一个点，到它的最大拥挤度的最小值肯定是

与它相邻的一个点的此值和他们之间的边权值取一个max，然后在所有max中取一个min！

这样我们就可以想到只要把板子里的松弛稍微修改一下，即只需把原本的求和改为取max就ok了！

另，注意此题应构无向图！！

代码

#include<bits/stdc++.h>
using namespace std;
inline int gi() {
    int x=0,w=0;char ch=0;
    while(!(ch>='0'&&ch<='9')) {
        if(ch=='-') w=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return w?-x:x;
}               //读入优化
const int maxn=3e5+1;
const int maxm=1e5+1;
priority_queue< pair<int,int> > q；//大根堆（后变小根堆）
int n,m,s,t,head[maxm],tot,dis[maxm],vis[maxm];
struct Edge {
    int next,now,w;
}edge[maxn];        
void make(int from,int to,int t) {
    edge[++tot].next=head[from];
    edge[tot].now=to;
    edge[tot].w=t;
    head[from]=tot;
}                   //链式前向星存图
void dijkstra() {
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty()) {
        int x=q.top().second; q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=edge[i].next) {
            int k=max(dis[x],edge[i].w),r=edge[i].now;
            //取max而不取和
                if(k<dis[r]) {
                    dis[r]=k;
                    q.push(make_pair(-dis[r],r)); 
                    //取一个负就可以变为小根堆！！
                }
        }
    }

}
int main()
{
    n=gi(); m=gi(); s=gi(); t=gi();
    for(int i=1,x,y,z;i<=m;i++) {
        x=gi(); y=gi(); z=gi();
        make(x,y,z);
        make(y,x,z);
        //构无向图
    }
    dijkstra();
    printf("%d",dis[t]);
    return 0;
}