当前位置:   article > 正文

2021 RoboCom 7-3 打怪升级 (dijkstra+floyd)(好题!题型:“双权值“+路径记录)

7-3 打怪升级

分析:这道题目我们首先要找到一个起点,使得这个起点到其他所有点的最大距离尽可能地小,所以我们只能分别以每个点作为原点跑一遍最短路,这样就可以求出来最佳原点,当然这个过程我们可以直接用floyd来实现。

剩下的就是我们用最佳原点跑一边dijkstra求一下满足题意的最佳路径即可,就是改一下dijkstra更新的条件以及加一个pre数组来记录一下路径。

用dijkstra来更新最优路径(),太帅了!

:经典else if   封神!

  1. for(int i=1;i<=n;i++)
  2. {
  3. if(d[i]>d[begin]+w1[begin][i])//代价优先选择小的
  4. {
  5. d[i]=d[begin]+w1[begin][i];
  6. w[i]=w[begin]+w2[begin][i];
  7. pre[i]=begin;
  8. q.push({d[i],i});
  9. }
  10. else if(d[i]==d[begin]+w1[begin][i])//在代价相同时优先选择武器价值高的
  11. {
  12. if(w[i]<w[begin]+w2[begin][i])
  13. {
  14. w[i]=w[begin]+w2[begin][i];
  15. pre[i]=begin;
  16. q.push({d[i],i});
  17. }
  18. }
  19. }

ACcode: 

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=1e3+10;
  4. typedef pair<int,int>PII;
  5. long long f[N][N],w1[N][N],w2[N][N];
  6. long long d[N],w[N],pre[N],st[N],tt;
  7. bool vis[N];
  8. int n,m,k;
  9. void dijkstra(int x)
  10. {
  11. priority_queue<PII,vector<PII>,greater<PII> >q;
  12. q.push({0,x});
  13. memset(d,0x3f,sizeof d);d[x]=0;
  14. while(!q.empty())
  15. {
  16. int begin=q.top().second;
  17. q.pop();
  18. if(vis[begin]) continue;
  19. vis[begin]=true;
  20. for(int i=1;i<=n;i++)
  21. {
  22. if(d[i]>d[begin]+w1[begin][i])//代价优先选择小的
  23. {
  24. d[i]=d[begin]+w1[begin][i];
  25. w[i]=w[begin]+w2[begin][i];
  26. pre[i]=begin;
  27. q.push({d[i],i});
  28. }
  29. else if(d[i]==d[begin]+w1[begin][i])//在代价相同时优先选择武器价值高的
  30. {
  31. if(w[i]<w[begin]+w2[begin][i])
  32. {
  33. w[i]=w[begin]+w2[begin][i];
  34. pre[i]=begin;
  35. q.push({d[i],i});
  36. }
  37. }
  38. }
  39. }
  40. }
  41. int main()
  42. {
  43. cin>>n>>m;
  44. memset(f,0x3f,sizeof f);
  45. memset(w1,0x3f,sizeof w1);
  46. memset(w2,-0x3f,sizeof w2);
  47. for(int i=1;i<=m;i++)
  48. {
  49. int u,v;
  50. scanf("%d%d",&u,&v);
  51. scanf("%lld%lld",&w1[u][v],&w2[u][v]);
  52. f[v][u]=f[u][v]=w1[v][u]=w1[u][v];w2[v][u]=w2[u][v];
  53. }
  54. for(int i=1;i<=n;i++) f[i][i]=0;
  55. for(int k=1;k<=n;k++)
  56. for(int i=1;i<=n;i++)
  57. for(int j=1;j<=n;j++)
  58. f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
  59. long long ans=0x3f3f3f3f3f3f3f3f;
  60. int x=0;
  61. for(int i=1;i<=n;i++)
  62. {
  63. long long t=0;
  64. for(int j=1;j<=n;j++)
  65. t=max(t,f[i][j]);
  66. if(t<ans)//记录最大距离的最小值
  67. {
  68. ans=t;
  69. x=i;
  70. }
  71. }
  72. for(int i=1;i<=n;i++) pre[i]=i;
  73. dijkstra(x);
  74. printf("%d\n",x);
  75. int k;
  76. cin>>k;
  77. while(k--)
  78. {
  79. int t;
  80. scanf("%d",&t);
  81. tt=0;
  82. while(x!=t)
  83. {
  84. st[++tt]=t;
  85. t=pre[t];
  86. }
  87. printf("%d",x);
  88. for(int i=tt;i>=1;i--)
  89. printf("->%d",st[i]);
  90. if(tt)
  91. printf("\n%lld %lld\n",d[st[1]],w[st[1]]);
  92. else
  93. printf("\n%lld %lld\n",d[x],w[x]);
  94. }
  95. return 0;
  96. }

over~

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

闽ICP备14008679号