代碼：https://github.com/jinhang/2016_Huawei_SoftWareMatch
前言
賽題源自“未來網絡”業務發放中的路由計算問題。算路問題屬于基礎算法問題，在圖論、網絡、交通等各個方面均有着廣泛的研究與運用，裡面不乏一些經典的算法，例如最短路中的廣度優先搜尋，Dijkstra算法等。網絡算路問題的更優算法實作對于網絡資源高效配置具有重要價值。
本次大賽分為初賽、複賽和總決賽三個主要階段，目前為總決賽/複賽階段。
總決賽/複賽賽題描述
1 問題定義
給定一個帶權重的有向圖G=(V,E)，V為頂點集，E為有向邊集，每一條有向邊均有一個權重。對于給定的頂點s、t，以及V的子集V’和V’’，尋找從s到t的兩條不成環的有向路徑P’和P’’，使得P’經過V’中所有的頂點，而P’’經過V’’中所有的頂點（對P’經過V’中頂點的順序以及P’’經過V’’中頂點的順序不做要求）。
若不同時存在這樣的兩條有向路徑，則輸出無解，程式運作時間越短，則視為結果越優； 若同時存在這樣的兩條有向路徑，則輸出得到的兩條路徑，按下列優先級從高到低評價結果優劣：
1、 路徑P’和P’’重合的有向邊個數越少，則視為結果越優；
2、 在兩條路徑重合的有向邊個數一樣的情況下，兩條路徑權重總和越少，則視為結果越優；
3、 在上述兩個名額一樣的情況下，程式運作時間越短，則視為結果越優。
說明：
1）圖中所有權重均為[1,100]内的整數；
2）任一有向邊的起點不等于終點；
3）連接配接頂點A至頂點B的有向邊可能超過一條，其權重可能一樣，也可能不一樣；
4）該有向圖的頂點不會超過2000個，每個頂點出度（以該點為起點的有向邊的數量）不超過20；
5）V’和V’’中元素個數均不超過100，交集為空，且不包含起始頂點s和終止頂點t；
6）從s到t的不成環有向路徑P是指，P為由一系列有向邊組成的從s至t的有向連通路徑，且不允許重複經過任一頂點；
7）路徑的權重是指所有組成該路徑的所有有向邊的權重之和（重複邊的權重應分别在兩條路徑中各計算一次）。
2 輸入與輸出
輸入檔案格式
以兩個.csv檔案（csv是以逗号為分隔符的文本檔案）給出輸入資料，一個為圖的資料(G)，一個為需要計算的路徑資訊(s,t,V’,V’’)。檔案每行以換行符（ASCII’\n’即0x0a）為結尾。
1）圖的資料中，每一行包含如下的資訊：
LinkID,SourceID,DestinationID,Cost
其中，LinkID為該有向邊的索引，SourceID為該有向邊的起始頂點的索引，DestinationID為該有向邊的終止頂點的索引，Cost為該有向邊的權重。頂點與有向邊的索引均從0開始編号(不一定連續，但用例保證索引不重複)，頂點索引範圍在[0，2000)，有向邊索引範圍在[0，40000)。
2）路徑資訊中，隻有一行如下資料：
DemandID,SourceID,DestinationID,IncludingSet
其中，DemandID裡面第一行為1，第二行為2，表示路徑索引，1表示P’，2表示P’’，SourceID為起始頂點s的索引，DestinationID為終止頂點t的索引，IncludingSet表示必須經過的頂點集合V’或V’’，其中不同的頂點索引之間用“ | ”分割，如果該路徑沒有必經頂點要求，則此處輸入NA。
輸出檔案格式
輸出檔案同樣為一個.csv 檔案。
1）如果該測試用例存在滿足要求的有向路徑P’和P’’，則輸出兩行資訊，第一行按P’經過的有向邊順序，依次輸出有向邊的索引，索引之間用“ | ”分割；第二行按P’’經過的有向邊順序依次輸出有向邊的索引，索引之間用“ | ”分割；
2）如果該測試用例不同時存在兩條滿足要求的有向路徑P’和P’’，則隻輸出一行資訊：NA；
3）每一行隻允許輸出最多一條有向路徑，以換行符0x0a結尾。
3 單個用例的評分機制
有解用例的排名機制
按下面流程對參賽者結果進行排名：
Step1： 對于送出的結果，進行合法性檢驗(詳見題目描述)；
Step2： 程式運作時間不得超過10s；
若不滿足上述的結果則本用例得分為0；
Step3： 路徑P’和P’’重合的有向邊個數（不考慮權重）越少，排名越優；
Step4： 在路徑P’和P’’重合的有向邊個數一樣的情況下，計算P’和P’’的權重和，權重越小，排名越優；
Step5： 在上述兩個名額一樣的情況下，用程式運作時間細化排名，時間越短，排名越優。
無解用例的排名機制
按下列流程對參賽者結果進行排名：
Step1： 對于送出的結果，驗證是否識别出該用例無解，若無法識别或者程式運作時間超10s，則本用例得分為0；
Step2： 用程式的運作時間進行排名，時間越短，排名越優。
單個用例的評分标準如下：
根據上面排名流程得到的排名，使用标準分計分(排名第一的送出者為100分)。
若所有人均未得到正确結果，則所有人均得分為0。
4 網站系統判分機制
複賽階段官方網站開放接收複賽程式送出，系統平台會使用N個測試用例線上判題，參賽者對于每個測試用例都會得到一個百分制分數，使用算術平均分為該參賽者的最終得分，并展示在各區域複賽排行榜中。
特别說明：複賽階段的線上判題評分及排行僅供參賽者參考，不納入最終複賽成績。
5 簡單用例說明
在如上圖所示的有向圖中，我們會得到下面的有向圖資訊：
0,0,1,1
1,1,2,1
2,2,3,1
3,1,4,1
4,4,3,1
5,0,5,1
6,5,2,1
如果此時需要尋找從0到3的路徑P’和P’’，且P’必須經過頂點1，P’’必須經過頂點2，相應的路徑資訊檔案内容為：
1,0,3,1
2,0,3,2
對于該用例，可以找到如下兩組解:
0|1|2
5|6|2
以及
0|3|4
由于第一組解兩條路徑的重合邊個數為1，第二組解兩條路徑的重合邊個數為0。是以此時最優解應該是0|3|4，5|6|2。
6 複賽賽制說明
各區域晉級複賽隊伍為32-36隊，複賽采用分區域現場競賽的形式開展，共分成三個小階段：
1、 排位賽：區域現場複賽當天，各區域将通過一個官方用例對進入複賽隊伍送出的程式進行判題評分并排序，排序前8名的隊伍将作為下一個階段分組賽8個小組的種子隊，其餘隊伍通過抽簽方式進行分組。
2、 分組賽：區域共分8個小組，各小組采用單循環對戰方式競賽，通過積分（每場比賽勝得3分，平各得1分，負得0分）進行小組排序，排序前2名的隊伍小組出線進入下一階段的淘汰晉級賽。
3、 淘汰晉級賽：各小組出線隊伍組成16強，分成上下半區進行兩兩對戰淘汰晉級賽，分為“1/8決賽→1/4決賽→半決賽→決賽”，最後決出區域4強進入全國總決賽。
兩隊對戰規則說明：
1、 複賽分組賽和淘汰晉級賽均采用兩隊對戰的形式，每場對戰9局5勝。（分組賽勝積3分，負積0分，平各積1分，最後排序積分相同情況下，排位賽成績靠前者勝出；淘汰賽出現平局，則由官方提供用例“加時賽”決出勝負）；
2、 對戰雙方（如紅方、藍方）各需提供2個自設計用例，官方提供5個用例，共9個用例分9局進行對戰，用例發放順序為：紅方1→藍方1→紅方2→藍方2→官方1→官方2→官方3→官方4→官方5；
3、 每局對戰中，如由于己方提供用例導緻自己計算不出，則該局對方自動勝出，其餘依據“單個用例評分機制”判定勝負。
7 總決賽賽制說明
各區域複賽前四名共32支隊伍晉級總決賽，總決賽采用現場競賽的形式開展，共分成三個小階段：
1、 排位賽：總決賽當天，組委會将通過兩個官方比賽用例對進入總決賽賽隊伍送出的程式進行判題評分并排序。各參賽隊根據排位賽評分排名進行分檔，1-8名定為種子隊（第一檔），9-16名為第二檔，17-24名為第三檔，25-32名為第四檔。排位賽排名僅供分組賽抽簽使用，不影響參賽隊伍最終排名；
2、 分組賽：全國32強共分8個小組，分組過程采用抽簽進行，種子隊抽簽至A1-H1位置，第二檔隊伍抽簽至A2-H2位置，第三檔隊伍抽簽至A3-H3位置，第四檔隊伍抽簽至A4-H4位置，形成小組賽分組。各小組采用單循環對戰方式競賽，通過積分（每場比賽勝得3分，平各得1分，負得0分）進行小組排序，排序前2名的隊伍小組出線進入下一階段的淘汰晉級賽。如遇積分相同情況，将根據“淨勝局多-勝負關系占優-上傳時間早”的優先級進行排序；
3、 淘汰晉級賽：各小組出線隊伍組成16強，分成上下半區進行兩兩對戰淘汰晉級賽，分為“1/8決賽→1/4決賽→半決賽→決賽”，最後決出全國總冠軍。
1、 總決賽分組賽和淘汰晉級賽均采用兩隊對戰的形式，每場對戰9局5勝。（分組賽允許出現平局，淘汰賽出現平局，則 “上傳時間早”的隊伍勝出）；
3、 每局對戰中，如由于己方提供用例導緻自己計算不出，則該局對方自動勝出。官方提供用例如雙方均未計算出正确路徑，則雙方均不得分。其餘依據“單個用例評分機制”判定勝負。
8 關于參賽隊自行生成對戰測試用例的說明
由官方在複賽階段提供若幹完整用例作為選手生成用例的素材，選手可自行編輯用例（如删增頂點、有向邊、必經頂點、修改起始終止頂點等），或完全自行設計用例，隻需保證用例符合題目要求且有解。官方将通過大賽網站給進入複賽的參賽隊開放用例設計工具。
9 總決賽/複賽注意事項
1、 核心算法禁止使用第三方代碼；
2、 如參考有論文或第三方代碼，必須在readme檔案中提供來源說明；
3、 針對所有用例必須使用同一個算法和同一套代碼實作。
初賽賽題描述
給定一個帶權重的有向圖G=(V,E)，V為頂點集，E為有向邊集，每一條有向邊均有一個權重。對于給定的頂點s、t，以及V的子集V'，尋找從s到t的不成環有向路徑P，使得P經過V'中所有的頂點(對經過V'中節點的順序不做要求)。
若不存在這樣的有向路徑P，則輸出無解，程式運作時間越短，則視為結果越優；若存在這樣的有向路徑P，則輸出所得到的路徑，路徑的權重越小，則視為結果越優，在輸出路徑權重一樣的前提下，程式運作時間越短，則視為結果越優。
1）圖中所有權重均為[1，20]内的整數；
4）該有向圖的頂點不會超過600個，每個頂點出度(以該點為起點的有向邊的數量)不超過8；
5）V'中元素個數不超過50；
6）從s到t的不成環有向路徑P是指，P為由一系列有向邊組成的從s至t的有向連通路徑，且不允許重複經過任一節點；
7）路徑的權重是指所有組成該路徑的所有有向邊的權重之和。
以兩個.csv 檔案(csv 是以逗号為分隔符的文本檔案)給出輸入資料，一個為圖的資料(G)，一個為需要計算的路徑資訊(s,t,V')。檔案每行以換行符(ASCII'\n'即0x0a)為結尾。
其中，LinkID 為該有向邊的索引，SourceID 為該有向邊的起始頂點的索引，DestinationID為該有向邊的終止頂點的索引，Cost 為該有向邊的權重。頂點與有向邊的索引均從0 開始 編号(不一定連續，但用例保證索引不重複)。
SourceID,DestinationID,IncludingSet
其中，SourceID 為該路徑的起點，DestinationID 為該路徑的終點，IncludingSet 表示必須經過的頂點集合V'，其中不同的頂點索引之間用'|'分割。
1）如果該測試用例存在滿足要求的有向路徑P，則按P 經過的有向邊順序，依次輸出有向邊的索引，索引之間用'|'分割；
2）如果該測試用例不存在滿足要求的有向路徑P，則輸出兩個字元NA；
3）隻允許輸出最多一條有向路徑。
Step3： 計算送出的路徑的權重，權重越小，排名越優；
Step4： 在權重相同的結果裡，用程式運作時間進行排名，時間越短，排名越優。
Step1： 對于送出的結果，驗證是否識别出該用例無解，若無法識别或者算法運作時間超10s，則本用例得分為0；
4 最終得分機制
平台會使用N個測試用例判題，該N個測試用例分為初級、中級、進階三個等級，參賽者對于每個測試用例都會得到一個百分制分數，使用權重平均分(初級權重為0.2，中級權重為0.3，進階權重為0.5)作為該參賽者的最終得分。
特别說明：在比賽初期，平台隻放出初級、中級的測試用例，故此時滿分為50分，在比賽後期，才會放出進階測試用例（具體發放時間會在網站公告通知），此時滿分才為100分，請各位參賽者注意。
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 64位，核心版本 Linux version 3.13.0-24-gineric
SDK：為友善選手做題，分别提供c++(相容c）和Java SDK包供參考（見賽題下載下傳包），較長的描述資訊請見SDK目錄下的readme.txt。