[計算幾何]USACO Feb08 USACO Silver Game of Lines 連線遊戲

Title: 連線遊戲

Input: lines.in

Output: lines.out

Time Limit: 1000 ms

Memory Limit: 16 MB

Level: ★☆

Farmer John最近發明瞭一個遊戲，來考驗自命不凡的貝茜。遊戲開始的時候，FJ會給貝茜一塊畫著N (2 <= N <= 200)個不重合的點的木板，其中第i個點的橫、縱座標分別為X_i和Y_i (-1,000 <= X_i <=1,000；-1,000 <= Y_i <= 1,000)。

貝茜可以選兩個點畫一條過它們的直線，當且僅當平面上不存在與畫出直線平行的直線。遊戲結束時貝茜的得分，就是她畫出的直線的總條數。為了在遊戲中勝出，貝茜找到了你，希望你幫她計算一下最大可能得分。

程序名: lines

[多源最短路]USACO 奶牛聚會 spart

譯: zqzas

N(1 ≤ N ≤ 1000)個農場中的每個農場都有一隻奶牛去參加位於第X個農場的聚會.共有M (1 ≤ M ≤ 100,000)條單向的道路,每條道路連接一對農場.通過道路i會花費Ti (1 ≤ Ti ≤ 100)的時間.

作爲參加聚會的奶牛必須走到聚會的所在地(農場X).當聚會結束時,還要返回各自的農場.奶牛都是很懶的,她們想找出花費時間最少的路線.由於道路都是單向的,所有她們前往農場X的路線可能會不同於返程的路線.

Of all the cows, what is the longest amount of time a cow must spend walking to the party and back? 對於所有參加聚會的奶牛,找出前往聚會和返程花費總時間最多的奶牛,輸出這隻奶牛花費的總時間.

[次短路徑]HAOI2005 路由選擇問題 route 解題報告

路由選擇問題

【問題描述】

    X城有一個含有N個節點的通信網絡，在通信中，我們往往關心資訊從一個節點I傳輸到節點J的最短路徑。遺憾的是，由於種種原因，線路中總有一些節點會出故障，因此在傳輸中要避開故障節點。

任務一：在己知故障節點的情況下，求避開這些故障節點，從節點I到節點J的最短路徑S0。

任務二：在不考慮故障節點的情況下，求從節點I到節點J的最短路徑S1、第二最短路徑S2。

【輸入文件】

第1行： N I J (節點個數 起始節點 目標節點)

第2—N+1行： Sk1 Sk2…SkN (節點K到節點J的距離爲SkJ K=1，2，……，N)

最後一行： P T1 T2……Tp (故障節點的個數及編號)

【輸出文件】

S0 S1 S2 (S1<=S2 從節點I到節點J至少有兩條不同路徑)