|
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 |
#include <iostream> #include <sstream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <list> #include <stack> using namespace std; #define MAXN 0x3f3f3f3f struct edgeType{ int to; int cost; edgeType(int ito,int icost){ to = ito; cost = icost; } }; struct vertexType{ vector<edgeType> edge; int cost; int level; vertexType(int icost,int ilevel){ edge.clear(); cost = icost; level = ilevel; } }; int main(){ int m = 0,n = 0; while (cin >> m >> n) { vector<vertexType> vertex; for (int i = 0; i < n; i++) { int vcost,vlevel,vsub; cin >> vcost >> vlevel >> vsub; vertexType now(vcost,vlevel); while (vsub--) { int to,cost; cin >> to >> cost; edgeType tmp(to-1,cost); now.edge.push_back(tmp); } vertex.push_back(now); } int maxlv = vertex[0].level,minlv = vertex[0].level; bool vis[105]; int dis[105]; memset(vis, 0, sizeof(vis)); memset(dis, 0x3f3f, sizeof(dis)); dis[0] = vertex[0].cost; while (true) { int cur = -1; int mindis = MAXN; for (int i = 0; i < vertex.size(); i++) { if (vis[i]) { continue; } if (dis[i] < mindis) { mindis = dis[i]; cur = i; } } if (cur == -1) break; vertexType nowvertex = vertex[cur]; vis[cur] = true; maxlv = max(nowvertex.level,maxlv); minlv = min(nowvertex.level,minlv); //int nowlv = nowvertex.level; for (int i = 0; i < vertex[cur].edge.size(); i++) { edgeType nextedge = vertex[cur].edge[i]; vertexType nextvertex = vertex[nextedge.to]; if (max(abs(maxlv-nextvertex.level),abs(minlv-nextvertex.level)) > m) { continue; } int newcost = dis[cur] - nowvertex.cost + nextedge.cost + nextvertex.cost; if (newcost < dis[nextedge.to]) { dis[nextedge.to] = newcost; } } } int res = MAXN; for (int i = 0; i < n; i++) { res = min(dis[i], res); } cout << res << endl; } return 0; } |
这个题是一个比较基准有些多的最短路（和之前那个Dirt挺像）。
（这里的cost就是dijkstra算法里面的dis值）每一次更新下一节点时，下一节点的cost值为（当前cost值－当前点权＋下一边边权＋下一点点权）；每一次到达节点后，都根据当前抽出的节点的地位值，更新当前走过节点的地位的最大最小值，等接下来更新临接节点时，如果下一节点的地位与当前最大最小值中任意一个只差绝对值>m就要抛弃。以这两个为基准，进行正常的dijkstra，然后从头到尾的扫一遍cost数组，把最小值输出来就是答案。
