7-3 打怪升级 单源最短路

7-3 打怪升级
分数 25
作者 陈越
单位 浙江大学
dgsj.JPG

很多游戏都有打怪升级的环节，玩家需要打败一系列怪兽去赢取成就和徽章。这里我们考虑一种简单的打怪升级游戏，游戏规则是，给定有 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

邻接矩阵忘记初始化了，调试了2个小时🤮🤮🤮

#include<bits/stdc++.h>

using namespace std;
const int N=1004,INF=0x3f3f3f3f;
int g[N][N],vv[N][N];
int dist[N],s[N],f[N];
bool st[N];
int n,m;

void djs(int u){
	memset(dist,0x3f,sizeof dist);
	memset(st,0,sizeof st);
	memset(s,0,sizeof s);
	memset(f,0,sizeof f);
	dist[u]=0;
	s[u]=0;
	f[u]=u;
	for(int i=1;i<=n;++i)
	{
		int t=-1;
		for(int j=1;j<=n;++j)
		{
			if(st[j]==false&&(t==-1||dist[j]<dist[t]))t=j;
		}
		st[t]=true;
		for(int j=1;j<=n;++j){
			if(dist[j]>dist[t]+g[t][j]){
				dist[j]=dist[t]+g[t][j];
				s[j]=s[t]+vv[t][j];
				f[j]=t;
			}else if(dist[j]==dist[t]+g[t][j]){
				if(s[j]<s[t]+vv[t][j]){
					s[j]=s[t]+vv[t][j];
					f[j]=t;
				}
			}
		}
	}
}

void dfs(int x,int &s)
{
	if(f[x]==x){
		cout<<x;return;
	}
	else {
		s+=vv[x][f[x]];
		//cout<<f[x];
		//if(f[f[x]]==x)cout<<"NO";
		dfs(f[x],s);
		cout<<"->"<<x;
	}
}
int main(){
    memset(g,0x3f,sizeof g);
	cin>>n>>m;
	while(m--)
	{
		int x,y,w,v;
		cin>>x>>y>>w>>v;
		g[x][y]=g[y][x]=w;
		vv[x][y]=vv[y][x]=v;
	}
	int u=1,len=INF;
	for(int i=1;i<=n;++i)
	{
		djs(i);
		int ma=0;
		for(int j=1;j<=n;++j){
			ma=max(ma,dist[j]);
		}
		if(ma<len){
			len=ma;
			u=i;
		}
	}
	cout<<u<<endl;
	int k;cin>>k;

	djs(u);
	while(k--){
		int x;cin>>x;
		int ss=0;
		dfs(x,ss);
		cout<<endl;
		cout<<dist[x]<<" "<<s[x]<<endl;
	}
	return 0;
}

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