zoj 1221

先解釋一下題目的意思，看了我好久。。。;英語不好又不仔細看的人真心傷不起。。。。。

輸入19行表示的是 第 i 行就是第 i 個數字相鄰的城市的個數的多少，然後輸入相鄰的城市，隻算比 i 大的數，小的就不算了

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1221

解釋一下dijkstra 和 flody 差別 

dijkstra 是不能有負數邊的，因為他每次加入都是目前最小權值的邊和對應的

結點，如果有負數邊，可能再下一次再加另一個結點之後，該結點到原先已經加入的結點的邊為負數，則會導緻原來的算法不正确。因為如果已經通路過的結點，就預設已經找到最小路徑了，而實際上是可能通過一條負數邊而使他的路徑變得更小的。

FLODY

算法則因為是所有都要周遊過，就是通過一個結點，兩個結點，直到n-1個結點。。每次隻留下最短的，最後一次性得到到所有結點的最小路徑，是以可以有負數邊。

個人拙見。。。

都現在都有點理不清最短路徑和最小生成樹的那些算法，等有時間了一定要好好理清一下。。。

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>// 1221.cpp : Defines the entry point for the console application.</code>

<code>//好像沒有必要用floyd的感覺。。。。。試一下吧</code>

<code>//#include "stdafx.h"</code>

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

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

<code>using</code>

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

<code>int</code> <code>A[21][21];</code><code>//存邊的數組</code>

<code>int</code>

<code>max = 9;</code><code>//最大值 路不通</code>

<code>main()</code>

<code>{</code>

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

<code>data, sum, from, to, n, start = 1;</code>

<code>    </code><code>//memset(A, max, sizeof(A));</code>

<code>    </code><code>while</code>

<code>(~</code><code>scanf</code><code>(</code><code>"%d"</code><code>, &amp;sum))</code><code>//目前結點相鄰邊的個數</code>

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

<code>        </code><code>for</code>

<code>(</code><code>int</code> <code>i = 1; i &lt;= 20; i++)</code>

<code>(</code><code>int</code> <code>j = 1; j &lt;= 20; j++)</code>

<code>            </code><code>A[i][j] = 9;</code>

<code>        </code><code>while</code>

<code>(sum--)</code>

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

<code>            </code><code>scanf</code><code>(</code><code>"%d"</code><code>, &amp;data);</code>

<code>            </code><code>A[data][1] = A[1][data] = 1;</code><code>//表示通路，可以到達</code>

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

<code>(</code><code>int</code> <code>i = 2; i &lt; 20; i++)</code><code>//輸入19行資料</code>

<code>            </code><code>A[i][i] = 0;</code><code>//通路标志</code>

<code>            </code><code>scanf</code><code>(</code><code>"%d"</code><code>, &amp;sum);</code>

<code>            </code><code>while</code>

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

<code>                </code><code>scanf</code><code>(</code><code>"%d"</code><code>, &amp;data);</code>

<code>                </code><code>A[data][i] = A[i][data] = 1;</code><code>//表示通路，可以到達</code>

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

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

<code>//      for (int j = 1; j &lt;= 20; j++)</code>

<code>//      {</code>

<code>//          cout &lt;&lt; A[i][j] &lt;&lt; "  ";</code>

<code>//          if (j == 20)</code>

<code>//              cout &lt;&lt; endl;</code>

<code>//      }</code>

<code>(</code><code>int</code> <code>k = 1; k &lt;= 20; k++)</code>

<code>(</code><code>int</code> <code>j = 1; j &lt;= 20; j++)    </code><code>//一次Folyd算法記錄所有點間的最短路徑</code>

<code>        </code><code>if</code>

<code>(A[i][j] &gt; A[i][k] + A[k][j])</code>

<code>            </code><code>A[i][j] = A[i][k] + A[k][j];</code>

<code>        </code><code>scanf</code><code>(</code><code>"%d"</code><code>, &amp;n);</code>

<code>        </code><code>printf</code><code>(</code><code>"Test Set #%d\n"</code><code>, start++);</code>

<code>(n--)</code>

<code>            </code><code>scanf</code><code>(</code><code>"%d%d"</code><code>, &amp;from, &amp;to);</code>

<code>            </code><code>printf</code><code>(</code><code>"%d to %d: %d\n"</code><code>, from, to, A[from][to]);</code>

<code>        </code><code>printf</code><code>(</code><code>"\n"</code><code>);</code>

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

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

<code>0;</code>

<code>}</code>