输入
1 3 3 1 2 3 1 3 4 2 3 5
输出
Scenario #1: 4
思路：从1到n有很多条路径，每个路径能够承载的重量由该路径中最小的边决定。题目求的是路径能够承担的最大重量。例如：1–2--4–6，最小边是3；1–3--4–6 最小边是4; 1–2--5–6最小边是2； 所以能承担的最大重量是4，所在的通路是1–3--4–6；
这样的话我们可以对dijkstra算法进行改造，节点更新改为最小值大的更新。
if(dist[v] < min(dist[u],edge[i].w) ) dist[v] = min(dist[u],edge[i].w);
也就是每次先从V-S中找到一个最大值，该最大值也就是找到V-S中dist已经更新完毕后的那个（这个稍微一思考就明白）;然后判断该节点 u的临界点 v是否在u的加入下 dist[v] < min(dist[u],edge[i].w) ,成立则进行dist的更新，同时将该节点加到队列中。
参考代码
#include<iostream> #include<queue> #include<string.h> using namespace std; const int maxn = 1000+10; const int INF = 0x3f3f3f3f; int T,n,m,num,head[maxn],dist[maxn],vis[maxn];//vis:标记该点是否已加入到V中(该点已找到路径中可以的承载最大重量) struct Edge{ int next,to,w; }edge[maxn*maxn]; void add(int u,int v,int w){ edge[++num].next = head[u]; edge[num].to = v; edge[num].w = w; head[u] = num; } void dijkstra(int x){ priority_queue<pair<int,int> >q;//默认按照第一个字段进行比较,第一个字段相同再进行第二个字段比较. 比较时最大值优先级高. memset(vis,0,sizeof(vis)); memset(dist,0,sizeof(dist)); dist[x] = INF; q.push(make_pair(dist[x],x)); while(!q.empty()){ int u = q.top().second;//获取一个u 从V-S中找到一个最大的然后加入V q.pop(); if(vis[u]){//如果已经找到则进行下一个 continue; } vis[u] = 1; //做标记 if(vis[n]){//如果已经到n则结束 return; } for(int i = head[u]; i; i = edge[i].next){ int v = edge[i].to; if(vis[v]){//如果已找到..则结束. 注意:先找到的 必定是符合的.因为 在那一刻它是最大的,而其他到它可能是0或者更小. continue; } if(dist[v] < min(dist[u],edge[i].w) ){// 如果u-->v,且dist[v] < min(dist[u],edge[i].w),说明到v节点,可以承载更大的重量,然后更新v并将其加入到. dist[v] = min(dist[u],edge[i].w); q.push(make_pair(dist[v],v));// 这里面不会出现 dist相同,v不同的情况.因为在if里面我们就已经pass掉了. } } } } int main() { int u,v,w,i; i = 0; cin>>T; while(T--){ num = 0;//每次一定要进行初始化啊, 不然会发生... memset(head,0,sizeof(head)); cin>>n>>m; while(m--){ cin>>u>>v>>w; add(u,v,w); add(v,u,w);//这是一个无向图 } dijkstra(1); cout<<"Scenario #"<<++i<<":"<<endl; cout<<dist[n]<<endl<<endl; } return 0; }
补充：优先队列priority_queue()内部实现是堆，方法有top,pop,push等。 pair 是个有序对，类似于map，但需要把两个数据结合到一块时，可以使用。优先队列存放pair时，会先按照第一个数据进行优先级排序，第一个数据相同再按照第二个数据。默认最大值优先。如果想要小的优先，可以前面加个负号进行处理。
