题目：有n个数，每个数都由10个数字组成。并输入int costs[10];作为传递时间。每两个数之间要是有一位不同或有两位可以通过交换得到则这两个数可以互相传递，且传递时间为costs[有多少位相同的前缀]。输出从第一个数到最后一个数所要的最短时间。
解析：最短路径问题。记录两两之间的时间，用Dijkstra算法求解。
代码解析：
建议写代码前阅读以下条目
1. 存储数的方式可以是string，但是最好是long long，所占位数少，但对最终结果及是否通过没有太大关系。string好判断更简单，用long long判断比较烦，看个人喜好了。
2. 如果你卡在TLE(Time Limit Exceeded)8见此条。若用两个for循环依次记录相互之间的可达性会卡在Test 8。因为输入N非常大，导致超时。解决办法：建立所有数字/字符串的哈希表（map），改变每个数字一位/两位，看是否有相同的数字/字符串在输入中。因为哈希表的查找迅速，尽管改变次数多，但依旧比两个for循环来得快。
3. 如果你卡在WA(Wrong Answer)3见此条。你写的Dijkstra路径记录错误，Dijkstra算法是会更新路径，不是简单的输出此迭代得到的路径最短的点。
4. 如果你卡在WA8见此条。计算可达两点距离时出现错误，可能你写成了if(i == j)应写if(int(name[i] – ‘0’) == j)←对于储存形式为string来说。
5. 如果你卡在MLE(Memory Limit Exceeded)11见此条。在Dijkstra算法中只需要当前point相邻的点即可，并不需要全部的。最好不要在结构体中加入类似于unordered_map <Point*, int> neighbor;导致每个点都储存了可达点的数据，很容易造成内存溢出，并且没有这必要，造成内存浪费。记得new不用之后要delete。
7. 为了更加节省内存，你可以修改unordered_map <Point*, int> neighbor;为vector <int, int> neighbor;这样可能你放在结构体里面也不会MLE。
6. 推荐:
INF = 0x3f3f3f3f;
neighbor用unordered_map存储
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
#include<iostream> #include<unordered_map> #include<map> #include<vector> #include<set> #define INF 0x3f3f3f3f using namespace std; int costs[10]; int n; vector<int>result; map<long long, int>names; struct Point { Point(int i) { distence = INF; done = false; index = i; } long long name; Point* parent; long long distence; bool done; int index; }; unordered_map<Point*, int>* neighbor; vector<Point>point; void cal_diff(Point* pointNow) { delete neighbor; neighbor = new unordered_map<Point*, int>; map<long long, int>::iterator ptr; long long name = pointNow->name; long long temp; for (int i = 0; i < 10; i++) { temp = name - name % long long(pow(10, i + 1)) / long long(pow(10, i)) * long long(pow(10, i)) - long long(pow(10, i));; for (int j = 0; j < 10; j++) { temp += long long(pow(10, i)); if (temp == name)continue; ptr = names.find(temp); if (ptr != names.end()) (*neighbor).insert({ &point[ptr->second], costs[9 - i] }); } } for (int i = 0; i < 10; i++) { int a = name % long long(pow(10, i + 1)) / long long(pow(10, i)); for (int j = i + 1; j < 10; j++) { int b = name % long long(pow(10, j + 1)) / long long(pow(10, j)); temp = name + long long(pow(10, i)) * (b - a) + long long(pow(10, j)) * (a - b); ptr = names.find(temp); if (ptr != names.end()) (*neighbor).insert({ &point[ptr->second], costs[9 - j] }); } } } void dijkstra() { set<pair<int, Point*>>queue; point[0].distence = 0; queue.insert(make_pair(0, &point[0])); Point* now; unordered_map<Point*, int>::iterator ptr; while (!queue.empty()) { now = queue.begin()->second; if (now->index == n) return; queue.erase(queue.begin()); if (now->done) continue; cal_diff(now); now->done = true; for (ptr = neighbor->begin(); ptr != neighbor->end(); ptr++) { Point* n = ptr->first; int cost = ptr->second; if (!n->done && n->distence > now->distence + cost) { n->parent = now; n->distence = now->distence + cost; queue.insert(make_pair(n->distence, n)); } } } } void chaseBack() { result.push_back(n); Point* pointTemp = point[n - 1].parent; while (pointTemp != &point[0]) { result.insert(result.begin(), pointTemp->index); pointTemp = pointTemp->parent; } result.insert(result.begin(), 1); } int main() { cin >> n; for (int i = 0; i < 10; i++)cin >> costs[i]; for (int i = 0; i < n; i++) { point.push_back(*new Point(i + 1)); cin >> point[i].name; names.insert({ point[i].name, i }); } dijkstra(); if (point[n - 1].distence >= INF) cout << -1 << endl; else { chaseBack(); cout << point[n - 1].distence << endl; cout << result.size() << endl; for (auto i : result)cout << i << " "; } } |
浙公网安备 33010902002953号