题目电波： POJ–1797 Heavy Transportation
n点m条边， 求1到n最短边最大的路径的最短边长度
改进dijikstra，dist[i]数组保存源点到i点的最短边最大的路径的最短边长度
#include<iostream>#include<cstring>#include<algorithm>#include<stdio.h>using namespace std;#define maxn 100010#define inf 0x3f3f3f3fstruct ac{ int x,y; ac(){} ac(int a,int b){ x=a,y=b; }}a[maxn];struct wa{ int to,va,nex;}eg[maxn];int dis[maxn],head[maxn];bool fa[maxn];int n,m,tot,len;void init(){ memset(head,-,sizeof(head)); memset(eg,,sizeof(eg)); memset(fa,,sizeof(fa)); tot=,len=;}void add_eg(int u,int v,int va){ eg[tot].to=v; eg[tot].va=va; eg[tot].nex=head[u]; head[u]=tot++; eg[tot].to=u; eg[tot].va=va; eg[tot].nex=head[v]; head[v]=tot++;}bool xxx(ac q,ac w){ ; ;}void add(int v){ ) return ; ])){ swap(a[v],a[v/]); add(v/); }}void updata(int v){ >len) return ; ==len){ ],a[v])) swap(a[v],a[v*]); return ; } ])&&xxx(a[v],a[v*+])) return ; ],a[v*+])){ swap(a[v*],a[v]); updata(v*); }else{ swap(a[v*+],a[v]); updata(v*+); }}void dijstra(){ memset(dis,,sizeof(dis)); memset(fa,,sizeof(fa)); dis[]=inf; a[++len]=ac(inf,); while(len){ ac x=a[]; int u=x.y; swap(a[],a[len--]),updata(); if(fa[u]) continue; fa[u]=; ;j=eg[j].nex){ int v=eg[j].to; int va=eg[j].va; if(dis[v]<min(dis[u],va)){ dis[v]=min(dis[u],va); a[++len]=ac(dis[v],v); add(len); } } }}int main(){ ; cin>>t; while(t--){ cin>>n>>m; init(); ;j<m;j++){ int u,v,va; scanf("%d%d%d",&u,&v,&va); add_eg(u,v,va); } dijstra(); printf("Scenario #%d:\n%d\n\n",zz++,dis[n]); }}
