很多游戏都有打怪升级的环节，玩家需要打败一系列怪兽去赢取成就和徽章。这里我们考虑一种简单的打怪升级游戏，游戏规则是，给定有 N 个堡垒的地图，堡垒之间有道路相连，每条道路上有一只怪兽把守。怪兽本身有能量，手里的武器有价值。打败怪兽需要的能量等于怪兽本身的能量，而怪兽一旦被打败，武器就归玩家所有 —— 当然缴获的武器价值越高，玩家就越开心。
你的任务有两件：
- 帮助玩家确定一个最合算的空降位置，即空降到地图中的某个堡垒，使得玩家从这个空降点出发，到攻下最难攻克（即耗费能量最多）的那个堡垒所需要的能量最小；
- 从这个空降点出发，帮助玩家找到攻克任意一个其想要攻克的堡垒的最省能量的路径。如果这种路径不唯一，则选择沿途缴获武器总价值最高的解，题目保证这种解是唯一的。
输入格式:
输入第一行给出两个正整数 N (≤1000) 和 M，其中 N 是堡垒总数，M 是怪兽总数。为简单起见，我们将堡垒从 1 到 N 编号。随后 M 行，第 i 行给出了第 i 只怪兽的信息，格式如下：
B1 B2 怪兽能量 武器价值其中
B1和B2是怪兽把守的道路两端的堡垒编号。题目保证每对堡垒之间只有一只怪兽把守，并且怪兽能量和武器价值都是不超过 100 的正整数。再后面是一个正整数 K（≤N）和玩家想要攻克的 K 个目标堡垒的编号。
输出格式:
首先在一行中输出玩家空降的堡垒编号
B0。如果有多种可能，则输出编号最小的那个。随后依次为玩家想要攻克的每个堡垒
B推荐最省能量的攻克路径，并列出需要耗费的能量值和沿途缴获武器的总价值。注意如果最省力的路径不唯一，则选择沿途缴获武器总价值最高的解。格式为：B0->途经堡垒1->...->B 总耗费能量 武器总价值输入样例:
6 12 1 2 10 5 2 3 16 20 3 1 4 2 2 4 20 22 4 5 2 2 5 3 12 6 4 6 8 5 6 5 10 5 6 1 20 25 1 5 8 5 2 5 2 1 2 6 8 5 4 2 3 6 5输出样例:
5 5->2 2 1 5->1->3 12 7 5->4->6 10 7 5 0 0代码长度限制
16 KB
时间限制
5000 ms
内存限制
64 MB
栈限制
8192 KB
思路：就是一个找最短路的问题，其实就是多加了一个条件，就是判断每条路带来的价值，怪不得分了25分，我的话跑了n个单源最短路这样。我看题解很多人用了floyd，但其实用dij的话优先队列可能复杂度会再降一下吧，但是n要是特别大的话数组重置会花很长时间，考虑这个的话那就还是floyd比较快。
#include "bits/stdc++.h" using namespace std; int n, m; struct edge { int to, w, v; edge(int a, int b, int c){ to = a, w = b, v = c; } }; struct point{ int id; int dis; int val; point(int a, int b, int c){ id = a, dis = b, val = c; } bool operator < (const point & a) const { if(dis != a.dis) return dis > a.dis; else return val < a.val; } }; vector<edge> g[1100]; int pre[1100]; void print(int x){ if(pre[x] == 0) { cout<<x; return; } print(pre[x]); cout<<"->"<<x; } int minn = INT_MAX; int vis[1100]; int dis[1100]; int val[1100]; int target; int maxdis; int maxval; void dij(int x){ memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); memset(val, 0, sizeof(val)); memset(pre, 0, sizeof(pre)); dis[x] = 0; target = 0; maxdis = 0; maxval = 0; priority_queue<point> q; q.push(point(x, dis[x], val[x])); while(q.size()){ point t = q.top(); q.pop(); if(vis[t.id]) continue; //已经找到最短路的就不用再找了 vis[t.id] = 1; for(int i = 0; i < g[t.id].size(); i ++){ edge tt = g[t.id][i]; if(vis[tt.to]) continue; if(dis[tt.to] > t.dis + tt.w || (dis[tt.to] == t.dis + tt.w && val[tt.to] < t.val + tt.v) ) { dis[tt.to] = t.dis + tt.w, val[tt.to] = t.val + tt.v; pre[tt.to] = t.id; q.push(point(tt.to, dis[tt.to], val[tt.to])); } } if(dis[t.id] > maxdis || dis[t.id] == maxdis && maxval < val[t.id]) maxdis = dis[t.id], maxval = val[t.id], target = t.id; } } int main(){ int k; int begin; cin>>n>>m; int a, b, c, d; for(int i = 0; i < m; i ++){ cin>>a>>b>>c>>d; g[a].push_back(edge(b, c, d)); g[b].push_back(edge(a, c, d)); } for(int i = 1; i <= n; i ++){ dij(i); if(maxdis < minn) minn = maxdis, begin = i; } cin>>k; cout<<begin<<endl; dij(begin); int x; for(int i = 0; i < k; i ++){ cin>>x; print(x); cout<<endl; cout<<dis[x]<<" "<<val[x]; if(i != k - 1) cout<<endl; } return 0; }
