首页 > 代码库 > 最短最优升级路径（完美世界2017秋招真题）
最短最优升级路径（完美世界2017秋招真题）
题目说明：
游戏网站提供若干升级补丁，每个补丁大小不一，玩家要升级到最新版，如何选择下载哪些补丁下载量最小。
输入
第一行输入 第一个数为用户版本 第二个数为最新版本，空格分开
接着输入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<iostream>
2 #include<vector>
3
4 using namespace std;
5
6 pair<int,vector<int>> minPatch(vector<int> &oldVersion, vector<int> &newVersion, vector<int> &patch, int start, int end){
7 //pair的第一个参数是该最小补丁的大小，第二个参数是start到底i个补丁的最小时的下载线路
8 vector<pair<int,vector<int>>> minPatch;
9 vector<int>fv;
10 fv.push_back(start);
11 pair<int, vector<int>>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<int, vector<int>>cur;
41 vector<int> curPatch(minPatch.at(minIndex).second);
42 curPatch.push_back(newVersion.at(curIndex));
43 cur.first = minPatch.at(minIndex).first + patch.at(curIndex);
44 cur.second = curPatch;
45 if (newVersion.at(curIndex) == end){
46 return cur;
47 }
48 minPatch.push_back(cur);
49 }
50 return minPatch.at(minPatch.size() - 1);
51 }
52
53 int main(){
54 vector<int>oldV,newV,patch;
55 int start,end;
56 cin>>start>>end;
57 int o,n,p;
58 while(cin >>o >> n >> p){
59 oldV.push_back(o);
60 newV.push_back(n);
61 patch.push_back(p);
62 }
63 pair<int,vector<int>> paths = minPatch(oldV,newV,patch,start,end);
64 vector<int>::iterator it = paths.second.begin();
65 while(it != paths.second.end()){
66 cout << (*it);
67 ++it;
68 if(it != paths.second.end()) cout<< "->";
69 }
70 cout << "(" << paths.first <<")";
71 return 0;
72 }
最短最优升级路径（完美世界2017秋招真题）