洛谷 P1339 [USACO09OCT]热浪Heat Wave（用Dij)

2019-11-06 07:57:19

字体：大中小

来源：转载

供稿：网友

题目题解代码

题目

FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 <= T <= 2,500)个城镇，方便地标号為1到T。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用（包括油费，过路费等等）。

给定一个地图，包含C (1 <= C <= 6,200)条直接连接2个城镇的道路。每条道路由道路的起点Rs，终点Re (1 <= Rs <= T; 1 <= Re <= T)，和花费(1 <= Ci <= 1,000)组成。求从起始的城镇Ts (1 <= Ts <= T)到终点的城镇Te(1 <= Te <= T)最小的总费用。

题解

虽然说这道题可以用最简单快捷的3个for轻松搞定，但是鉴于对Dijkstra的不熟悉，我写了单源最短路Dij Dij过程： d[i]放从起点s到所有点的路程。 a[u,v]放从u到v的路程 b[i]放从起点s到i点的最短路是否求过 a)初始化： d和a全都弄成很大的数 for i 1——n d[i]=a[s,i]//所有可以从1直接到的点 b)repeat

找一个没有求过最短路且距起点最近的点u 若存在u则用d[u]去更新别的点 i=1——n d[i]=d[u]+a[u,i](d[i]>d[u]+a[u,i]&i点没有求完最短路) b[u]标记为求过until u=0

时间复杂度O(n2) $时间复杂度O(n^2)$

代码

var i,j,n,m,s,t,x,y:longint; a:array[1..3000,1..3000]of longint; d:array[0..3000]of longint; b:array[0..3000]of boolean;PRocedure dij;var i,j,min,u:longint;begin for i:=1 to n do d[i]:=a[s,i]; repeat u:=0;min:=maxlongint; for i:=1 to n do if (d[i]<min)and b[i] then begin min:=d[i]; u:=i; end; if u>0 then begin b[u]:=false; for i:=1 to n do if b[i] and (d[u]+a[u,i]<d[i]) then d[i]:=d[u]+a[u,i]; end; until u=0;end;begin readln(n,m,s,t); fillchar(a,sizeof(a),$7f); fillchar(b,sizeof(b),true); fillchar(d,sizeof(d),$7f); b[s]:=false; for i:=1 to m do begin readln(x,y,j); a[x,y]:=j;a[y,x]:=j; end; dij; writeln(d[t]);end.

上一篇：图的最小生成树---Prim算法

下一篇：Boost库的简介与安装

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注