当前位置:   article > 正文

PTA星际探险

PTA星际探险

作者 周强

单位 青岛大学

在某个遥远的未来,新新人类将可能这样进行星际探险:宇宙中分布着若干个跳跃点,人类飞船在每个跳跃点可超光速跳至其它跳跃点。当然,一般来说每次跳跃是要消耗一定能量的,但因为有未知物质的影响,某些跳跃反而可以获得一定能量。

在所有跳跃点中,人类的原始家园——地球最具特殊性,这是唯一一个“不是任何跳跃的目的地”的跳跃点,换句话说,从地球可以跳到其它点,但是从任何其它点都不能跳到地球。

假设有一艘飞船从地球出发开始星际探险之旅,考虑到旅行成本,设定在到达目的地时能量的消耗上限,那么有一些跳跃点是飞船在这个能量消耗限制下能够抵达的,而有一些跳跃点是无法抵达的。现在请你编程找出所有能够抵达的跳跃点。

需要注意的几点:

  1. 一个能够抵达的跳跃点,是指飞船抵达这个点时,能量消耗在限制之内;所有能够抵达的点,指的是这类点的集合,而并不是指飞船某个单趟旅行一路上所经过的点。例如:飞船从地球出发,如果能量限制只够跳到比邻星或者天狼星这两个点之一,而无法在单趟旅行中先后抵达这两个点,但是“所有能够抵达的点”则包括这两个点,即从跳跃能力上看,这两个点均是“可以抵达”的。
  2. 某些跳跃可以让飞船增加能量,并且存在这种可能:从某个点开始,经过若干次跳跃,又回到这个点。但是能量规律决定了:回到这个点时,飞船的能量只可能比原先从这个点出发时低(否则将出现“永动机”)。
  3. 能量消耗上限,评判的是抵达目的地(某个跳跃点)时所消耗的能量,而不考虑中途点的能量状态。须知有的跳跃会增加能量,所以完全可能出现这种情况:跳到A点时,能量消耗超过限制,但从A点跳到B点恰好是增加能量,并且跳到B时,总的能量消耗不超过限制。此时认为A点不可抵达、B点可抵达。

输入格式:

首先在一行中给出正整数NN<=2000),是宇宙中跳跃点的数量。

接下来N行,第i行(i=1..N)按以下格式描述编号为i的跳跃点的信息:

k p1 d1 p2 d2 ... pk dk (以空格间隔)

其中:整数k是从这个跳跃点出发,能跳到其它点的数量,之后的k非零整数pi dipi表示能跳到的某个点的编号,di表示飞船跳到pi点的能量变化,如果di为正表示这个跳跃会增加能量(增加di),di为负表示这个跳跃要消耗能量(消耗的值为|di|)。题目保证从地球到任何一个可以抵达的跳跃点,沿途消耗(或增加)的能量之和的绝对值不超过108。

最后一行给出正整数E,表示飞船出发时设置的能量消耗上限。

输出格式:

按照编号从小到大的顺序输出飞船所有能够抵达的跳跃点编号,每行输出一个编号(行末有换行符)。

提示:

  1. “地球”这个跳跃点总是被认为“可以抵达”的,并且抵达这个点不需要消耗能量(因为这是出发点)。
  2. 地球的编号不一定是1

输入样例:

在这里给出一组输入。例如:

  1. 6
  2. 3 2 -3 4 -5 3 -6
  3. 1 6 -6
  4. 2 4 -2 5 -2
  5. 2 3 -3 6 -3
  6. 1 4 4
  7. 0
  8. 7

输出样例:

在这里给出相应的输出。例如:

  1. 1
  2. 2
  3. 3
  4. 4
  5. 6

题目大致意思:n个星球,然后给1~n个星球从它们出发能到星球的个数k,然后给k*2个数,前一个数为能到的星球,后一个数为燃料变化。燃料有可能增加,并且燃料消耗完飞船还能飞!

#吐槽:星际时代的人类到底点了什么黑科技,没燃料还能飞,燃料还能越飞越多?

地球(起点)是所有点无法到达的点(题目保证唯一)。

这一题主要是dijkstra算法,并且不用去约束燃料消耗完。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define endl "\n"
  5. #define P pair<ll,ll>
  6. const ll N = 2e3+7;
  7. ll n,m,k,sum;
  8. bool lian[N][N];
  9. ll v[N][N],value[N];
  10. bool vis[N];
  11. priority_queue<P ,vector<P>,greater<P> >q;
  12. void dj(){
  13. while(!q.empty()){
  14. ll x=q.top().second,y=q.top().first;
  15. q.pop();
  16. for(ll i = 1 ; i <= n ; i ++){
  17. if(lian[x][i] && value[x] + v[x][i] < value[i]){
  18. value[i] = value[x] + v[x][i];
  19. q.push({value[i],i});
  20. }
  21. }
  22. }
  23. return;
  24. }
  25. void solve(){
  26. cin >> n;
  27. ll x,y,c;
  28. memset(vis,1,sizeof vis);
  29. for(ll i = 1 ; i <= n ; i ++){
  30. cin >> m;
  31. for(ll j = 0 ; j < m ; j ++){
  32. cin >> x >> y;
  33. lian[i][x]=1;
  34. v[i][x]=-y;//取反,用来跑最短路
  35. vis[x]=0;
  36. }
  37. }
  38. for(ll i = 1 ; i <= n ; i ++)//找地球
  39. if(vis[i])c=i;
  40. cin >> k;
  41. memset(value,0x3f,sizeof value);
  42. q.push({0,c});
  43. value[c]=0;
  44. dj();
  45. for(ll i = 1 ; i <= n ; i ++)
  46. if(value[i] <= k)cout << i << endl;
  47. return ;
  48. }
  49. int main(){
  50. ll t=1;//cin >> t;
  51. while(t--)solve();
  52. return 0;
  53. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/714523
推荐阅读
相关标签
  

闽ICP备14008679号