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

【軟件介紹】

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

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

前言

賽題源自“未來網(wǎng)絡(luò)”業(yè)務(wù)發(fā)放中的路由計算問題。算路問題屬于基礎(chǔ)算法問題，在圖論、網(wǎng)絡(luò)、交通等各個方面均有著廣泛的研究與運用，里面不乏一些經(jīng)典的算法，例如最短路中的廣度優(yōu)先搜索，Dijkstra算法等。網(wǎng)絡(luò)算路問題的更優(yōu)算法實現(xiàn)對于網(wǎng)絡(luò)資源高效配置具有重要價值。

1、問題定義

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

說明：

1）圖中所有權(quán)重均為[1，20]內(nèi)的整數(shù)；

個人吐槽：沒有復(fù)權(quán)值，經(jīng)典Dijkstra算法可能適用
2）任一有向邊的起點不等于終點；

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

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

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

個人吐槽：指定點集越多，耗時越夸張，難點之一，優(yōu)化點之一。
6）從s到t的不成環(huán)有向路徑P是指，P為由一系列有向邊組成的從s至t的有向連通路徑，且不允許重復(fù)經(jīng)過任一節(jié)點；
7）路徑的權(quán)重是指所有組成該路徑的所有有向邊的權(quán)重之和。

2、輸入與輸出

輸入文件格式

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

輸出文件格式

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

3 單個用例的評分機制

有解用例的排名機制

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

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

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

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

Step3： 計算提交的路徑的權(quán)重，權(quán)重越小，排名越優(yōu)；

Step4： 在權(quán)重相同的結(jié)果里，用程序運行時間進行排名，時間越短，排名越優(yōu)。

無解用例的排名機制

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

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

Step2： 用程序的運行時間進行排名，時間越短，排名越優(yōu)。

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

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

4 最終得分機制

平臺會使用N個測試用例判題，該N個測試用例分為初級、中級、高級三個等級，參賽者對于每個測試用例都會得到一個百分制分數(shù)，使用加權(quán)平均分(初級權(quán)重為0.2，中級權(quán)重為0.3，高級權(quán)重為0.5)作為該參賽者的最終得分。
特別說明：在比賽初期，平臺只放出初級、中級的測試用例，故此時滿分為50分，在比賽后期，才會放出高級測試用例（具體發(fā)放時間會在網(wǎng)站公告通知），此時滿分才為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的路徑，且必須經(jīng)過頂點2和3，我們會得到如下的路徑信息：

0,1,2|3

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

運行環(huán)境

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