hdu1595find the longest of the shortest 最短路

分类：最短路

最短路

;const int maxn = 1110 ;const int inf = 0x3f3f3f3f;struct Edge{int u , v , w ;int next ;}edge[maxn*maxn] ;int head[maxn] ;int nedge ;int F[maxn] ;int vis[maxn] ;int dis[maxn] ;int a[maxn] ;int n , m;void addedge(int u , int v , int w){edge[nedge].u = u ;edge[nedge].v = v ;edge[nedge].w = w ;edge[nedge].next = head[u] ;head[u] = nedge++ ;}void dijkstra(int num){memset(vis , 0 , sizeof(vis)) ;for(int j = 2;j <= n;j++)dis[j] = inf ;dis[1] = 0 ;while(1){int mi = inf; int pos ;for(int j = 1 ;j <= n;j++)if(!vis[j] && dis[j] < mi)mi = dis[pos = j] ;if(mi == inf)break;vis[pos] = 1 ;for(int i = head[pos] ;i != -1 ;i = edge[i].next){if(i == num || i == (num^1))continue ;int v = edge[i].v;if(dis[v] > dis[pos] + edge[i].w){dis[v] = dis[pos] + edge[i].w ;F[v] = i ;}}}}int main(){//freopen(“in.txt” ,”r” , stdin) ;while(~scanf(“%d%d” , &n , &m)){memset(head , -1 , sizeof(head)) ;nedge = 0 ;memset(F , 0 , sizeof(F)) ;while(m–){int u , v , w ;scanf(“%d%d%d” ,&u , &v ,&w) ;addedge(u , v , w) ;addedge(v , u , w) ;}dijkstra(nedge) ;int u = n ;int ans = 0 ;int len = 0 ;while(1){if(u == 1)break ;a[++len] = F[u] ;u = edge[F[u]].u ;}for(int i = 1;i <= len;i++){dijkstra(a[i]) ;ans = max(ans , dis[n]) ;}cout<<ans<<endl;}return 0 ;}

上一篇hdu3339 In Action 最短路+01背包下一篇hdu1839Delay Constrained Maximum Capacity Path 二分+最短路

顶0踩0

，缘是浪漫的相遇，瞬间让你我的心化为永恒！

相关文章：

你感兴趣的文章：

标签云：