Huawei Code Craft華為軟件精英挑戰賽，這是國內科技公司華為舉行的大型軟件競賽，本軟件即是華為codecraft復賽用例，希望給喜歡和關注本次競賽的朋友一些幫助。

【軟件介紹】

注：本文文字均摘自官方指定網站和論壇，權威且可信，答疑見中間部分，非常全，眾玩家可放心閱讀。

同時文末給出了包括自己在內的諸多玩家的解法。

前言

賽題源自“未來網絡”業務發放中的路由計算問題。算路問題屬于基礎算法問題，在圖論、網絡、交通等各個方面均有著廣泛的研究與運用，里面不乏一些經典的算法，例如最短路中的廣度優先搜索，Dijkstra算法等。網絡算路問題的更優算法實現對于網絡資源高效配置具有重要價值。

1、問題定義

給定一個帶權重的有向圖G=(V,E)，V為頂點集，E為有向邊集，每一條有向邊均有一個權重。對于給定的頂點s、t，以及V的子集V'，尋找從s到t的不成環有向路徑P，使得P經過V'中所有的頂點(對經過V'中節點的順序不做要求)。
若不存在這樣的有向路徑P，則輸出無解，程序運行時間越短，則視為結果越優；若存在這樣的有向路徑P，則輸出所得到的路徑，路徑的權重越小，則視為結果越優，在輸出路徑權重一樣的前提下，程序運行時間越短，則視為結果越優。

說明：

1）圖中所有權重均為[1，20]內的整數；

個人吐槽：沒有復權值，經典Dijkstra算法可能適用
2）任一有向邊的起點不等于終點；

個人吐槽：極端情況被踢出，減小難度

3）連接頂點A至頂點B的有向邊可能超過一條，其權重可能一樣，也可能不一樣；

個人吐槽：不一樣就取較小者
4）該有向圖的頂點不會超過600個，每個頂點出度(以該點為起點的有向邊的數量)不超過8；
5）V'中元素個數不超過50；

個人吐槽：指定點集越多，耗時越夸張，難點之一，優化點之一。
6）從s到t的不成環有向路徑P是指，P為由一系列有向邊組成的從s至t的有向連通路徑，且不允許重復經過任一節點；
7）路徑的權重是指所有組成該路徑的所有有向邊的權重之和。

2、輸入與輸出

輸入文件格式

以兩個.csv 文件(csv 是以逗號為分隔符的文本文件)給出輸入數據，一個為圖的數據(G)，一個為需要計算的路徑信息(s,t,V')。文件每行以換行符(ASCII'\n'即0x0a)為結尾。
1）圖的數據中，每一行包含如下的信息：
LinkID,SourceID,DestinationID,Cost
其中，LinkID 為該有向邊的索引，SourceID 為該有向邊的起始頂點的索引，DestinationID為該有向邊的終止頂點的索引，Cost 為該有向邊的權重。頂點與有向邊的索引均從0 開始 編號(不一定連續，但用例保證索引不重復)。
2）路徑信息中，只有一行如下數據：
SourceID,DestinationID,IncludingSet
其中，SourceID 為該路徑的起點，DestinationID 為該路徑的終點，IncludingSet 表示必須經過的頂點集合V'，其中不同的頂點索引之間用'|'分割。

輸出文件格式

輸出文件同樣為一個.csv 文件。
1）如果該測試用例存在滿足要求的有向路徑P，則按P 經過的有向邊順序，依次輸出有向邊的索引，索引之間用'|'分割；
2）如果該測試用例不存在滿足要求的有向路徑P，則輸出兩個字符NA；
3）只允許輸出最多一條有向路徑。

3 單個用例的評分機制

有解用例的排名機制

按下面流程對參賽者結果進行排名：

Step1： 對于提交的結果，進行合法性檢驗(詳見題目描述)；

Step2： 程序運行時間不得超過10s；

若不滿足上述的結果則本用例得分為0；

Step3： 計算提交的路徑的權重，權重越小，排名越優；

Step4： 在權重相同的結果里，用程序運行時間進行排名，時間越短，排名越優。

無解用例的排名機制

按下列流程對參賽者結果進行排名：

Step1： 對于提交的結果，驗證是否識別出該用例無解，若無法識別或者算法運行時間超10s，則本用例得分為0；

Step2： 用程序的運行時間進行排名，時間越短，排名越優。

單個用例的評分標準如下：

根據上面排名流程得到的排名，使用標準分計分(排名第一的提交者為100分)。
若所有人均未得到正確結果，則所有人均得分為0。

4 最終得分機制

平臺會使用N個測試用例判題，該N個測試用例分為初級、中級、高級三個等級，參賽者對于每個測試用例都會得到一個百分制分數，使用加權平均分(初級權重為0.2，中級權重為0.3，高級權重為0.5)作為該參賽者的最終得分。
特別說明：在比賽初期，平臺只放出初級、中級的測試用例，故此時滿分為50分，在比賽后期，才會放出高級測試用例（具體發放時間會在網站公告通知），此時滿分才為100分，請各位參賽者注意。

5 簡單用例說明

在如上圖所示的有向圖中，我們會得到下面的有向圖信息：

0,0,1,1
1,0,2,2
2,0,3,1
3,2,1,3
4,3,1,1
5,2,3,1
6,3,2,1

如果此時需要尋找從0到1的路徑，且必須經過頂點2和3，我們會得到如下的路徑信息：

0,1,2|3

對于該用例，可以找到如下兩條可行路徑:
1|5|4
2|6|3
由于第一條路徑的權重為4，第二條路徑的權重為5，所以此時最優解應該1|5|4。

運行環境

CPU：Intel Xeon CPU E5-2690 V2 @ 3.00GHz
內存：2G
內核：單核
編譯器：gcc 4.8.4；java 1.7.0_95；
操作系統：linux Ubuntu 14.04.3 LTS，內核版本 Linux version 3.13.0-24-gineric