题目很长,但是意思就是给你n,A,B,C,D

n表示有n个城市 A是飞机的重量 B是一个常数表示转机代价 C是单位燃油的价格 D是一个常数

假设一个点到另外一个点的距离为整数L 起飞前的油量为f  则在这途中每飞行一单位距离 就花费(f+A)/D的燃油

#include <bits/stdc++.h>
typedef long long ll;
typedef long double lb;
using namespace std;
const int MAXN=,MAXM=;
int to[MAXM << ], nxt[MAXM << ], Head[MAXN], ed = ;
lb cost[MAXM << ];
int n;
inline void addedge(int u, int v, lb c) {
to[++ed] = v;
nxt[ed] = Head[u];
Head[u] = ed;
cost[ed] = c;
}
struct HeapNode {
int u;
lb d;
bool operator < (const HeapNode& rhs) const {
return d > rhs.d;
}
} zz;
lb mindist[MAXN];
bool vis[MAXN];
priority_queue<HeapNode> que;
void Hijkstra(int s) {
for (int i = ; i <= n; i++) {
mindist[i] = 4000000000000000000.0;
}
mindist[s] = 0.0;
memset(vis, , sizeof(vis));
zz.d = , zz.u = s;
que.push(zz);
while (!que.empty()) {
HeapNode x = que.top();
que.pop();
int u = x.u;
if (vis[u] || mindist[u] != x.d) {
continue;
}
vis[u] = true;
for (int v, i = Head[u]; i; i = nxt[i]) {
v = to[i];
if (mindist[v] > mindist[u] + cost[i]) {
mindist[v] = mindist[u] + cost[i];
//p[v]=u;
zz.d = mindist[v], zz.u = v;
que.push(zz);
}
}
}
}
void init(int x) {
ed = ;
for (int i = ; i <= x; i++) {
Head[i] = ;
}
}
struct node {
ll x, y;
} P[MAXN];
int main() {
int TC;
scanf("%d", &TC);
while (TC--) {
ll A, B, C, D;
scanf("%d %lld %lld %lld %lld", &n, &A, &B, &C, &D);
init(n);
for (int i = ; i <= n; i++) {
scanf("%lld %lld", &P[i].x, &P[i].y);
}
for (int i = ; i <= n; i++) {
for (int j = i + ; j <= n; j++) {
ll ax = abs(P[i].x - P[j].x);
ll ay = abs(P[i].y - P[j].y);
ll dis = ax * ax + ay * ay;
dis = ceil(sqrt(dis));
lb c = (pow((lb)D / (D - 1.0), dis) - 1.0) * A * C + B;
addedge(i,j,c),addedge(j,i,c);
}
}
Hijkstra();
printf("%.10Lf\n", mindist[n]);
}
return ;
}

最新文章

  1. 编译安装mmseg提示cannot find input file: src/Makefile.in错误
  2. ui-grid
  3. JNI ReferenceTable overflow
  4. ping命令脚本实现显示网络状态、学生姓名、学号
  5. 今天&lt;s:hidden&gt;突然能用了
  6. SSH集成步骤
  7. Vi Usage
  8. [Effective C++ --016]成对使用New和Delete时要采用相同形式
  9. localStorage、sessionStorage详解,以及storage事件使用
  10. Android 高级UI设计笔记01:使用ExpandableListView组件(ListView的扩展)
  11. android后台截屏实现(3)--编译screencap
  12. Hibernate中3种结果转换的详细说明(转)
  13. akka 入门
  14. JavaScript语法基础(1)
  15. LTS和其他解决方案的比较(官方)
  16. @ConditionalOnMissingBean注解理解
  17. Invalid Host header
  18. Vue利用canvas实现移动端手写板
  19. vbox 的 ova 提取vmdk 与 vdi 以及扩容
  20. unity3d中Transform组件变量详解

热门文章

  1. Spring A 标签链接使用
  2. mdk3洪水攻击教程
  3. 洛谷 题解 P1353 【[USACO08JAN]跑步Running】
  4. [转帖]sys.dm_exec_connections (Transact-SQL)
  5. kettle下载地址
  6. 【Python基础】06_Python中的函数
  7. LeetCode 答案(python)18-24
  8. 怎样获取所有的embed节点对象
  9. MongoDB实战读书笔记(二):面向文档的数据
  10. javaIO——LineNumberReader