Gym - 102141D 通项公式 最短路
2024-10-06 17:20:34
题目很长,但是意思就是给你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 ;
}
最新文章
- 编译安装mmseg提示cannot find input file: src/Makefile.in错误
- ui-grid
- JNI ReferenceTable overflow
- ping命令脚本实现显示网络状态、学生姓名、学号
- 今天<;s:hidden>;突然能用了
- SSH集成步骤
- Vi Usage
- [Effective C++ --016]成对使用New和Delete时要采用相同形式
- localStorage、sessionStorage详解,以及storage事件使用
- Android 高级UI设计笔记01:使用ExpandableListView组件(ListView的扩展)
- android后台截屏实现(3)--编译screencap
- Hibernate中3种结果转换的详细说明(转)
- akka 入门
- JavaScript语法基础(1)
- LTS和其他解决方案的比较(官方)
- @ConditionalOnMissingBean注解理解
- Invalid Host header
- Vue利用canvas实现移动端手写板
- vbox 的 ova 提取vmdk 与 vdi 以及扩容
- unity3d中Transform组件变量详解