題目：
一張有向圖，編號1 ~ M。
從1走最短路徑到2，再從2走最短路徑回到1
從1走最短路徑到3，再從3走最短路徑回到1
...
從M走最短路徑到2，再從M走最短路徑回到1
求走過的總距離
從1走最短路徑到2，再從2走最短路徑回到1
從1走最短路徑到3，再從3走最短路徑回到1
...
從M走最短路徑到2，再從M走最短路徑回到1
求走過的總距離
做法：
每個點皆做一次dijkstra(single source shortest path)，計算Dist[1][i]+D[i][1](1<i<=M)
這樣複雜度顯然太高，會超時。
從1走到所有點的最短路即是一次dijkstra。
而要再從那些點走回來的話，其實就將有向圖反邊，再從1做一次dijkstra，這時候從1走到各個點的距離就是原圖各點走到1的最短路徑。
兩次結果總和即為答案。
以下code中的G[2][maxn]，G[0]是存原圖，G[1]存反圖。
code:
沒有留言:
張貼留言