交互式多媒体网站开发,wordpress模板文件修改插件,山东联通网站备案,公司网站发布流程7-3 打怪升级 (25 分)
题意#xff1a;
很多游戏都有打怪升级的环节#xff0c;玩家需要打败一系列怪兽去赢取成就和徽章。这里我们考虑一种简单的打怪升级游戏#xff0c;游戏规则是#xff0c;给定有 N 个堡垒的地图#xff0c;堡垒之间有道路相连#xff0c;每条道路…7-3 打怪升级 (25 分)
题意
很多游戏都有打怪升级的环节玩家需要打败一系列怪兽去赢取成就和徽章。这里我们考虑一种简单的打怪升级游戏游戏规则是给定有 N 个堡垒的地图堡垒之间有道路相连每条道路上有一只怪兽把守。怪兽本身有能量手里的武器有价值。打败怪兽需要的能量等于怪兽本身的能量而怪兽一旦被打败武器就归玩家所有 —— 当然缴获的武器价值越高玩家就越开心。
你的任务有两件
帮助玩家确定一个最合算的空降位置即空降到地图中的某个堡垒使得玩家从这个空降点出发到攻下最难攻克即耗费能量最多的那个堡垒所需要的能量最小 从这个空降点出发帮助玩家找到攻克任意一个其想要攻克的堡垒的最省能量的路径。如果这种路径不唯一则选择沿途缴获武器总价值最高的解题目保证这种解是唯一的。
题解
这个空降位置我一开始没读懂后来才明白就是找一个点pos使得pos到其他点的最远距离最小因此我们需要先求出到其他所有点的距离可以用floyd来做复杂度为O(n3)O(n^3)O(n3)n1e3,我也不知道为啥能过。。 注意floyd枚举k要在最外层。。。我给忘了 然后就直接跑最短路就可以了两个关键词的最短路
代码
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, 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
#elsestartTime clock ();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn2e39;
struct node{int v,nen,val;
};
vectornodevec[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.nennen)return vala.val; return nena.nen;}
};
int pre[maxn];
int n,m;
void dij(int s){for(int i1;in;i){Dis[i]INF_int;pre[i]-1;}priority_queuenode2q;Dis[s]0;Val[s]0;q.push({s,0,0});while(!q.empty()){node2 nowq.top();q.pop();int unow.u;int nennow.nen;int valnow.val;if(vis[u])continue;vis[u]1;for(auto x:vec[u]){int vx.v;int wx.nen;int valx.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]wVal[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();cinnm;memset(dis,INF_int,sizeof(dis));for(int i1;im;i){int u,v;int nen,val;read(u,v,nen,val);
// cinuvnenval;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 k1;kn;k)for(int i1;in;i){for(int j1;jn;j){dis[i][j]min(dis[i][j],dis[i][k]dis[k][j]);}}pos-1;int maxxINF_int;
// for(int i1;in;i){
// for(int j1;jn;j){
// printf(%lld ,dis[i][j]);
// }
// printf(\n);
// }for(int i1;in;i){ll ans0;for(int j1;jn;j){ansmax(ans,dis[i][j]);}if(ansmaxx){maxxans;posi;}}coutposendl;dij(pos);int q;read(q);int x;for(int i1;iq;i){read(x);coutpos;print(x); coutendl;coutDis[x] Val[x]endl; }//Time_test();
}
