7-3 打怪升级 (25 分)

7-3 打怪升级 (25 分)

题意:

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

你的任务有两件:

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

题解:

这个空降位置,我一开始没读懂,后来才明白就是找一个点pos,使得pos到其他点的最远距离最小,因此我们需要先求出到其他所有点的距离,可以用floyd来做,复杂度为 O ( n 3 ) O(n^3) O(n3),n<=1e3,我也不知道为啥能过。。
注意:floyd枚举k要在最外层。。。我给忘了
然后就直接跑最短路就可以了,两个关键词的最短路

代码:

#include 
#include 
#define debug(a, b) printf("%s = %d\n", a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll= 1e18;
const int INF_int= 0x3f3f3f3f;
void read(){
     };
template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar)
{
     
    x= 0;
    char c= getchar();
    bool flag= 0;
    while (c < '0' || c > '9')
        flag|= (c == '-'), c= getchar();
    while (c >= '0' && c <= '9')
        x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();
    if (flag)
        x= -x;
    read(Ar...);
}
template <typename T> inline void write(T x)
{
     
    if (x < 0) {
     
        x= ~(x - 1);
        putchar('-');
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
void rd_test()
{
     
#ifdef ONLINE_JUDGE
#else
    startTime = clock ();
    freopen("data.in", "r", stdin);
#endif
}
void Time_test()
{
     
#ifdef ONLINE_JUDGE
#else
    endTime= clock();
    printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn=2e3+9;
struct node{
     
	int v,nen,val;
};
vector<node>vec[maxn];
ll dis[maxn][maxn];
int vis[maxn];
int Dis[maxn];
int Val[maxn];
struct node2{
     
	int u,nen,val;
	bool operator<(const node2 &a)const{
     
		if(a.nen==nen)return val<a.val; 
		return nen>a.nen;
	}
};
int pre[maxn];
int n,m;
void dij(int s){
     
	for(int i=1;i<=n;i++){
     
		Dis[i]=INF_int;
		pre[i]=-1;
	}
	priority_queue<node2>q;
	Dis[s]=0;
	Val[s]=0;
	
	q.push({
     s,0,0});
	while(!q.empty()){
     
		node2 now=q.top();
		q.pop();
		int u=now.u;
		int nen=now.nen;
		int val=now.val;
		if(vis[u])continue;
		vis[u]=1;
		for(auto x:vec[u]){
     
			int v=x.v;
			int w=x.nen;
			int val=x.val;
			if(Dis[v]>Dis[u]+w){
     
				pre[v]=u;
				Dis[v]=Dis[u]+w;
				Val[v]=Val[u]+val;
				q.push({
     v,Dis[v],Val[v]});
			}
			else if(Dis[v]==Dis[u]+w&&Val[v]<Val[u]+val){
     
				pre[v]=u;
				Val[v]=Val[u]+val;
				q.push({
     v,Dis[v],Val[v]});
			}
		}
	}
}
int pos;
void print(int x){
     
	if(pre[x]==-1)return ;
	print(pre[x]);
	cout<<"->"<<x;
}
int main()
{
     
    //rd_test();
	
	cin>>n>>m;
	memset(dis,INF_int,sizeof(dis));
	for(int i=1;i<=m;i++){
     
		int u,v;
		int nen,val;
		read(u,v,nen,val);
//		cin>>u>>v>>nen>>val;
		dis[u][v]=nen;
		dis[v][u]=nen;
		dis[u][u]=0;
		dis[v][v]=0;
		vec[u].push_back({
     v,nen,val});
		vec[v].push_back({
     u,nen,val});
	}
	for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++){
     
            for(int j=1;j<=n;j++){
     
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
	pos=-1;
	int maxx=INF_int;
//	for(int i=1;i<=n;i++){
     
//		for(int j=1;j<=n;j++){
     
//			printf("%lld ",dis[i][j]);
//		}
//		printf("\n");
//	}
	for(int i=1;i<=n;i++){
     
		ll ans=0;
		for(int j=1;j<=n;j++){
     
			ans=max(ans,dis[i][j]);
		}
		if(ans<maxx){
     
			maxx=ans;
			pos=i;
		}
	}
	cout<<pos<<endl;
	dij(pos);
	int q;
	read(q);
	int x;
	for(int i=1;i<=q;i++){
     
		read(x);
		cout<<pos;
		print(x); 
		cout<<endl;
		cout<<Dis[x]<<" "<<Val[x]<<endl; 
	}
    //Time_test();
}




你可能感兴趣的