锐客网

  1. 首页 > it技术 > >

#|7-3 打怪升级 (25 分)

【#|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 PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){ }; template 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 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; }; vectorvec[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 vala.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_queueq; 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]"<>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

    推荐阅读


    上一篇：测试工程师|软件测试就是简单的点点点吗（？？）

    下一篇：数据结构|【数据结构(C语言描述)】时空复杂度