[UVA] 104 Arbitrage

最短路徑的經典題目。arbitrage是fast trading最基本的套利方式，遙記得當初念書時，層幫一個firm 做利用CUDA 加速找arbitrage的實驗，那時候N好像是500以上...扯遠了。總之，這一題經過拆包裝後，就是在graph中，找出最少邊的negative cycle。

一開始使用Bellman Ford，想利用其detect negative cycle的性質。雖然BF是single source，但是因為graph是 completely connected，所以只需要做一個source即可確定圖中有無負環。BF的確是可以輕鬆判斷有無arbitrage的存在，可是在找出最少邊的負環路徑上很不給力。每個Vertex只記得最短路徑下其前一個vertex，我們可以找到"最賺錢的arbitrage"，但是對"最少邊"無能為力。

上網找了一下，發現這題用Floyd-Warshall更直覺容易懂，連結在這裡。只要稍稍改變relaxing的判斷式，FW可以拿來求任意pair在給定最大hub下，可行的最短路徑。在此題中，即為求最少hub下，是否有cycle是負數即可。


Relaxing 如下：

dist[N][N][N]  // 第三個index是hop 數
prev[N][N][N]

if (dist[i][j][hop] < dist[i][k][hop - 1] + edge[k][j]) {
   dist[i][j][hop] = dist[i][k][hop - 1] + edge[k][j];
   prev[i][j][hop] = k;  
}