Skip to content

Latest commit

 

History

History
47 lines (30 loc) · 2.34 KB

2011-11-23-pku-3767-i-wanna-go-home.md

File metadata and controls

47 lines (30 loc) · 2.34 KB
layout title date tags
post
[POJ] 3767 - I Wanna Go Home
2011-11-23
POJ
shortest path | 最短路徑
graph theory | 圖論

題目網址:3767 - I Wanna Go Home

題目概述

某國家正在面臨戰爭,國家中的城市分為兩派,分別支持不同的領導者。有一個商人想要回家,他要從城市 A 回到城市 B。現在要請你規劃出他最快能在多少時間內回到家。

Technique Detail

  • 城市數量 N,2 ≤ N ≤ 600
  • 道路數量 M,0 ≤ M ≤ 10,000
  • 道路花費時間 T,1 ≤ T ≤ 500
  • 每一條路線皆為雙向邊
  • 領導人的編號分別為 1 與 2
  • 假設商人總是要從編號為 1 的城市回到編號為 2 的城市
  • 編號為 1 的城市總是領導人 1 的派系,而編號為 2 的城市總是為領導人 2 的派系
  • 僅能通過一條連結不同派系城市的路

輸入格式

對於每筆測試資料的第一行輸入一個整數 N,表示該國家城市數量,若此數為 0 表示為測試資料結束。接著第二行輸入整數 M,代表該國家的道路數量。接著有 M 行,每行有三個數字 A, B, T,表示城市 A 與城市 B 之間有一條路徑,且需要耗費 T 的時間。測試資料的最後一行會輸入 N 個整數,這 N 個整數分別表示為各城市所代表的派系。

輸出格式

對於每一筆測試資料,輸出一個整數,表示該商人回家的最短時間。若無解時,請輸出 -1。


解題思路

在給定的條件中,我們可以發現,規劃出來的路線,僅能從派系 1 的城市走到派系 2 的城市,或是同派系之間的城市之間往返。因此可以看出不能從派系 2 的城市往派系 1 的城市走。(由僅能走一條跨派系的路線與起點城市皆屬於派系 1,終點城市皆屬於派系 2 可得知)

於是我們就可以針對給定的圖做點處理。原本整張圖上的邊皆為雙向邊,我們將連結兩個派系的邊化為單向邊,使該邊僅能由派系 1 的城市往派系 2 的城市。接著在使用一般的 shortest path 的演算法套入,即可解決此題。

Time Complexity: O(N × log N)

Source Code

<script src="https://gist.github.com/KuoE0/6154538.js"></script>

Source code on gist.