本文主要是介绍poj 3037 Skiing，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
//每个点的速度固定，与路径无关，SPFA
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const double inf=1e200;
const int maxn=10005;
double p2[105];
int h[105][105], n, pre[maxn], inqueue[maxn], cnt, v, r, c;
double ans, d[maxn];
struct node{
int v, w, next;
}edge[maxn*4];
void add_edge(int s, int e, int w){
edge[cnt].v=e;
edge[cnt].w=w;
edge[cnt].next=pre[s];
pre[s]=cnt++;
}
void init(){
int i, j, x, y;
p2[50]=1;
for(i=1; i<=50; i++){
p2[50-i]=p2[51-i]/2;
p2[50+i]=p2[49+i]*2;
}
memset(pre, -1, sizeof(pre));
cnt=0;
scanf("%d%d%d", &v, &r, &c);
n=r*c;
for(i=1; i<=r; i++)
for(j=1; j<=c; j++)
scanf("%d", &h[i][j]);
for(i=1; i<=r; i++)
for(j=1; j<=c; j++){
x=(i-1)*c+j;
if(i<r){
y=i*c+j;
add_edge(x, y, h[i][j]);
}
if(i>1){
y=(i-2)*c+j;
add_edge(x, y, h[i][j]);
}
if(j>1){
y=(i-1)*c+j-1;
add_edge(x, y, h[i][j]);
}
if(j<c){
y=(i-1)*c+j+1;
add_edge(x, y, h[i][j]);
}
}
}
bool spfa(int st){
int i, s, head;
for(i=1; i<=n; i++){
d[i]=inf;
inqueue[i]=0;
}
d[st]=0;
inqueue[st]=1;
queue<int >q;
q.push(st);
while(!q.empty()){
head=q.front();
q.pop();
inqueue[head]=0;
s=pre[head];
while(s!=-1){
if(d[edge[s].v]>d[head]+1.0/(p2[h[1][1]-edge[s].w+50]*v)){
d[edge[s].v]=d[head]+1.0/(p2[h[1][1]-edge[s].w+50]*v);
if(!inqueue[edge[s].v]){
inqueue[edge[s].v]=1;
q.push(edge[s].v);
}
}
s=edge[s].next;
}
}
return true;
}
int main(){
//freopen("1.txt", "r", stdin);
init();
spfa(1);
printf("%.2f\n", d[n]);
return 0;
}
这篇关于poj 3037 Skiing的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
