[最短路]打怪升级 2021RoboCom初赛C

很多游戏都有打怪升级的环节，玩家需要打败一系列怪兽去赢取成就和徽章。这里我们考虑一种简单的打怪升级游戏，游戏规则是，给定有 N 个堡垒的地图，堡垒之间有道路相连，每条道路上有一只怪兽把守。怪兽本身有能量，手里的武器有价值。打败怪兽需要的能量等于怪兽本身的能量，而怪兽一旦被打败，武器就归玩家所有 —— 当然缴获的武器价值越高，玩家就越开心。

你的任务有两件：

• 1. 帮助玩家确定一个最合算的空降位置，即空降到地图中的某个堡垒，使得玩家从这个空降点出发，到攻下最难攻克（即耗费能量最多）的那个堡垒所需要的能量最小；
• 1. 从这个空降点出发，帮助玩家找到攻克任意一个其想要攻克的堡垒的最省能量的路径。如果这种路径不唯一，则选择沿途缴获武器总价值最高的解，题目保证这种解是唯一的。

输入格式:

输入第一行给出两个正整数 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

题意： 给出一个连通图，先确定一个起点，该起点到最远点的距离最小，之后求出从该点到指定的k个点的最短路径，若长度相同则选择获得价值最高的那条，输出路径以及最短距离和获得的价值。

分析： 在确定起点时需要用到任意两点间最短路，所以可以先跑一个floyd，之后就可以得到起点，从起点开始dijkstra，过程中记录一下路径，要注意长度相等时的处理，剩下的就是套路了，仔细一点就不会出问题。

具体代码如下： 

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define pii pair
#define inf 0x3f3f3f3f
using namespace std;int dis[1005], n, m, dp[1005][1005], pre[1005], sum[1005];
bool vis[1005];
struct node{int to, d, w;//d表示距离，w表示价值 
};
vector g[1005];void dijkstra(int start){priority_queue, greater> q;dis[start] = 0;q.push(make_pair(dis[start], start));while(q.size()){int now = q.top().second;q.pop();if(vis[now]) continue;vis[now] = true;for(int i = 0; i < g[now].size(); i++){int to = g[now][i].to, d = g[now][i].d, w = g[now][i].w;if(dis[to] > dis[now]+d){dis[to] = dis[now]+d;pre[to] = now;sum[to] = sum[now]+w;q.push(make_pair(dis[to], to));}else if(dis[to] == dis[now]+d && sum[now]+w > sum[to]){sum[to] = sum[now]+w;pre[to] = now;}}}
}signed main()
{cin >> n >> m;for(int i = 1; i <= n; i++)dis[i] = inf;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)if(i != j)dp[i][j] = inf;for(int i = 1; i <= m; i++){int u, v, d, w;scanf("%d%d%d%d", &u, &v, &d, &w);g[u].push_back({v, d, w});g[v].push_back({u, d, w});dp[u][v] = d;dp[v][u] = d;}for(int k = 1; k <= n; k++)for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);int start, _min = inf;for(int i = 1; i <= n; i++){int t = 0;for(int j = 1; j <= n; j++)t = max(t, dp[i][j]);if(_min > t){_min = t;start = i;}}dijkstra(start);printf("%d\n", start);int k;cin >> k;for(int i = 1; i <= k; i++){int t;scanf("%d", &t);int now = t;vector path;while(now != 0){path.push_back(now);now = pre[now];} printf("%d", start);for(int i = path.size()-2; i >= 0; i--)printf("->%d", path[i]);puts("");printf("%d %d\n", dis[t], sum[t]);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！