poj 1553

題意：求1到2所有路徑中最小蛙跳   蛙跳：在一條路徑中所有蛙跳中的最大蛙跳

思路：dijska算法思想

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

<code>#include&lt;iostream&gt;</code>

<code>#include&lt;cmath&gt;</code>

<code>using</code>

<code>namespace</code> <code>std;</code>

<code>struct</code>

<code>Node</code>

<code>{</code>

<code>    </code><code>double</code>

<code>x,y;</code>

<code>}node[222];</code>

<code>double</code>

<code>dist[222];</code>

<code>int</code> <code>s[222];</code>

<code>int</code>

<code>n;</code>

<code>cas;</code>

<code>e(Node a,Node b)</code>

<code>    </code><code>return</code>

<code>sqrt</code><code>((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));</code>

<code>}</code>

<code>max(</code><code>double</code>

<code>x,</code><code>double</code>

<code>y)</code>

<code>    </code><code>if</code><code>(x&gt;y)</code><code>return</code>

<code>x;</code>

<code>    </code><code>return</code> 

<code>y;</code>

<code>void</code> 

<code>Dijsc()</code>

<code>    </code><code>int</code>

<code>i,j,v;</code>

<code>    </code><code>memset</code><code>(s,0,</code><code>sizeof</code><code>(s));</code>

<code>    </code><code>for</code><code>(i=1;i&lt;=n;i++)</code>

<code>        </code><code>dist[i]=e(node[1],node[i]);</code>

<code>    </code><code>s[1]=1;</code>

<code>    </code><code>{</code>

<code>        </code><code>v=-1;</code>

<code>        </code><code>double</code>

<code>min=999999999;</code>

<code>        </code><code>for</code><code>(j=2;j&lt;=n;j++)</code>

<code>        </code><code>{</code>

<code>            </code><code>if</code><code>(dist[j]&lt;min&amp;&amp;!s[j])  </code><code>//每次選擇最小蛙跳 向外擴充  所選擇的這個蛙跳肯定是最小的  也就是最優的</code>

<code>                </code><code>v=j,min=dist[j];</code>

<code>        </code><code>}</code>

<code>        </code> 

<code>        </code><code>if</code><code>(v==-1)</code><code>break</code><code>;s[v]=1;</code>

<code>        </code><code>for</code><code>(j=2;j&lt;=n;j++)</code><code>//通過最小的蛙跳向外擴充</code>

<code>            </code><code>if</code><code>((dist[j]&gt;dist[v])&amp;&amp;(dist[j]&gt;e(node[v],node[j])))</code>

<code>                </code><code>dist[j]=max(dist[v],e(node[v],node[j]));</code>

<code>    </code><code>}</code>

<code>printf</code><code>(</code><code>"Scenario #%d\n"</code><code>,cas);</code>

<code>printf</code><code>(</code><code>"Frog Distance = %.3f\n\n"</code><code>,dist[2]);</code>

<code>main()</code>

<code>i;</code>

<code>    </code><code>cas=0;</code>

<code>    </code><code>while</code><code>(</code><code>scanf</code><code>(</code><code>"%d"</code><code>,&amp;n)!=EOF)</code>

<code>        </code><code>if</code><code>(n==0)</code><code>break</code><code>;</code>

<code>        </code><code>cas++;</code>

<code>        </code><code>for</code><code>(i=1;i&lt;=n;i++)</code>

<code>            </code><code>scanf</code><code>(</code><code>"%lf%lf"</code><code>,&amp;node[i].x,&amp;node[i].y);</code>

<code>        </code><code>Dijsc();</code>

<code>0;</code>