题目说明：

游戏网站提供若干升级补丁，每个补丁大小不一，玩家要升级到最新版，如何选择下载哪些补丁下载量最小。

输入

第一行输入              第一个数为用户版本  第二个数为最新版本，空格分开

接着输入N行补丁数据        第一个数补丁开始版本 第二个数为补丁结束版本 第三个数为补丁大小，空格分开

输出

对于每个测试实例，输出一个升级路径以及最后实际升级的大小

时间限制

C/C++语言：1000MS

其他语言：3000MS

样例输入

1000 1050

1000 1020 50

1000 1030 70

1020 1030 15

1020 1040 30

1030 1050 40

1040 1050 20

样例输出

1000->1020->1040->1050(100)

思路：

本题自己想到的是Dijkstra算法.

设给定的旧版本好为o，要求的最新版本为n;

考虑有一个集合S={}，它保存从o到其他更新的版本的最少补丁大小的下载顺序和补丁的实际大小。

接着讲起始集合o添加到S中，

然后遍历给定的集合，找到更新的起始版本在S集合中、更新后的版本不在S集合中且补丁最小(这里的最小是从o出发到它更新后的版本的补丁之和的最小)的更新组合，找到后，将它加入集合S；

循环上面一步，知道找到o到n的最小更新方法。

用公式表示

起始状态：S={o}

假设其他版本分别是V={a b c d e f n}（相当于图的点集），可更新的方法用集合E（相当于图的边集）表示E={ev(ab),ev(bc),...};其中ev(ab)表示从a版本更新到b版本需要下载ev大小的补丁。

每次找满足下面条件的更新方法：

若ev(st)∈E，s∈S，t∉S,minev(ot) = min{ev(ot),ev(os) + ev(st)} = ev(os) + ev(st);则将t加入S集合。

 

1 #include
     
       2 #include
      
        3  4 using namespace std; 5  6 pair
       
        
         > minPatch(vector
         
           &oldVersion, vector
          
            &newVersion, vector
           
             &patch, int start, int end){ 7 //pair的第一个参数是该最小补丁的大小，第二个参数是start到底i个补丁的最小时的下载线路 8 vector
            
             
              
               >> minPatch; 9 vector
               
                fv;10 fv.push_back(start);11 pair
                

>first(0, fv); 12 minPatch.push_back(first); 13 while (true){ 14 int curMin = -1, curIndex,minIndex = -1;//minIndex保存当起始版本不是start时，其在minPatch中的位置 15 int len, pos;//如果起始版本在minPatch中存在，pos记录其位置 16 for (int i = 0; i < oldVersion.size(); i++){ 17 //标记当前补丁路线中的起始版本和最新版本是否在minPatch中已存在 18 //只有起始版本存在而最新版本不存在时，才合法 19 bool firFlag = false, secFlag = true; 20 //查找当前补丁路线中的目标版本是否已经在minPatch中 21 for (int j = 0; j < minPatch.size(); j++){ 22 len = minPatch.at(j).second.size() - 1; 23 //检验当前补丁路线中的起始版本是否在minPatch中已存在 24 if (oldVersion.at(i) == minPatch.at(j).second.at(len)){ 25 firFlag = true; 26 pos = j; 27 } 28 if (newVersion.at(i) == minPatch.at(j).second.at(len))secFlag = false;//检验当前补丁路线中的最新版本是否在minPatch中已存在 29 } 30 if (firFlag && secFlag){ 31 int p = minPatch.at(pos).first + patch.at(i); 32 if (curMin < 0 || p < curMin){//找到最小的合法新补丁 33 curMin = p; 34 curIndex = i; 35 minIndex = pos; 36 } 37 } 38 } 39 //添加新补丁进minPatch 40 pair