首页 > 代码库 > 题和题解：最"大"路
题和题解：最"大"路
题目：
【Description】
int getzuiduanlu(int x)
这是一行多么精妙的代码。
简明扼要的说明了这个函数要解决的问题。
现在我们就要解决一个最短路问题。
给定一张N点M边的无向图，求从点1到其余所有点的最短路。
这里的最短路指的是，从点1到某个点，边权最大的边最小的一条路径。
【Input】
跟我平时输入图的方法一样。要是看不懂就看样例吧。
【Output】
N-1行每行一个整数，第i行表示从点1到第i+1个点最短路中，边权最大的边的权值。
到不了输出-1。
【Sample Input】
3 3
1 2 1
2 3 1
1 3 2
【Sample Output】
1
1
【Hint】
20%：N, M <= 10
40%：N, M <= 1000
60%：N, M <= 100000
100%：N, M <=1000000
C++选手请注意对IO的优化。
时限2s；
这个题有人YY说要先跑个最小生成树，然后再跑搜索。我不信，先写个生成树然后再操作我觉得还算靠谱，但是考试时候还是在努力地被题目忽悠的往最短路上面想~~
事实上，最短路的思想也是正确的，对于标准的正解，大家还存在争议，不过，只要能做出来就行吧~~
好，现在先说我的最短路解法：
对 于spfa或者dijkstra，最短路中使用dis数组记录到达每个点的最短路总长，在这个题里面我们就可以想到用同样的算法来解决路径上最大边权值的 问题。我们只需要做一点点修改就可以巧妙的解决这个问题了~~当然这需要对最短路算法的深刻的理解才可以（偷笑~~我还真是不谦虚啊~~彪悍的人生不需要 低调，哈哈~~鄙视啊）~~
我所理解的我们的最短路算法的思想就是我们在没有整个图的时候，对于当前情况下维护一个当前的最优解，当我们遍历到更多的边和点的时候，如果能够优化我们以前求得的答案，我们就更改他。
所以，不难和这个题联想到一起。
只需要把我们的dis数组所保存的东西改一下就好了~~~
好了，现在我们来考虑一下怎么推出dis数组：
对 于当前的一个点x，我们便利它连的每一条边，下面用edge表示，终点记为t。然后我们现在（某个时刻）已经最短路一样的操作了一定的边，知道了x的 dis，也就是说我们从当前来说最优的一条路上走到x时候整条路上最大的一条边的权值记为dis[x]，然后我们只需要再从edge走过去就到达了t，那 么从当前路径到达t的最大边权值就是max(w,dis[x])，这一点是显而易见的。那么我们只需要比较这个max和dis[t]的值，将dis[t] 保存为较小的那一个就好了，这里只是对三角不等式进行修改就好，之后当我们整张图都更新完之后得到的就是最终答案，很显然吧。
好了，上代码：用了spfa，数据有一个点TLE了，用堆优dijkstra就能解决这个问题了。。。。。两秒时限还算良心。
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<cstring> 5 #define INF 70232024 6 #define MAXN 1000010 7 using namespace std; 8 struct edge 9 {10 int s,t,next;11 int w;12 }ed[2*MAXN];13 int tot=0,head[MAXN];14 int n,m;15 inline void add(int s,int t,int w)16 {17 ed[tot].s=s; ed[tot].t=t; ed[tot].w=w; ed[tot].next=head[s]; head[s]=tot++;18 }19 int dis[MAXN];20 bool vis[MAXN];21 inline void spfa()22 {23 queue <int> q;24 q.push(1);25 dis[1]=0;26 vis[1]=true;27 while(!q.empty())28 {29 int x=q.front();30 q.pop();31 vis[x]=false;32 for(int i=head[x];i!=-1;i=ed[i].next)33 {34 int t=ed[i].t,w=ed[i].w;35 int mx=dis[x]>w?dis[x]:w;36 if(dis[t]>mx)37 {38 dis[t]=mx;39 if(!vis[t])40 {41 q.push(t);42 vis[t]=true;43 }44 }45 }46 }47 }48 int main()49 {50 memset(head,-1,sizeof(head));51 cin>>n>>m;52 for(int i=1;i<=n;i++)dis[i]=INF;53 for(int i=1;i<=m;i++)54 {55 int a,b,c;56 scanf("%d%d%d",&a,&b,&c);57 add(a,b,c);58 add(b,a,c);59 }60 spfa();61 for(int i=2;i<=n;i++)62 {63 if(dis[i]==INF)printf("-1\n");64 else printf("%d\n",dis[i]);65 }66 return 0;67 }
题和题解：最"大"路