//ACCODE
/*
TASK: PKU_3037 - Skiing
LANG: C++
NAME: untitled.cpp
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>

#define RMAX 100
#define CMAX 100

using namespace std;

struct NODE
{
	int x,y;
	double time;
	NODE(){};
	NODE(int _x,int _y,double _time)
	{
		x = _x; y = _y; time = _time;
	}
};
bool operator <(const NODE &left,const NODE &right)
{
	return left.time>right.time; //here
}

int table[RMAX][CMAX];
bool vis[RMAX][CMAX];

int main()
{
	FILE *fin=NULL,*fout=NULL;
	fin = freopen("input.txt","r",stdin);
	fout = freopen("output.txt","w",stdout);

	//Dijkstra。 O(RClog(RC))

	int v,r,c; scanf("%d%d%d",&v,&r,&c);
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			scanf("%d",table[i]+j);
			if(!(0==i&&0==j)){
				table[i][j] -= table[0][0];
			}
		}
	}
	table[0][0] = 0;

	priority_queue<NODE> q; q.push(NODE(0,0,0.0l));
	for(int i=0;i<r;i++){
		fill(vis[i],vis[i]+c,false);
	}
	while(!q.empty()){
		NODE p=q.top(); q.pop();
		if(vis[p.x][p.y]){
			continue;
		}

		vis[p.x][p.y] = true;
		if(r-1==p.x&&c-1==p.y){
			printf("%.2lf\n",p.time); //here
			break;
		}

		double time=pow((double)2.0l,(double)table[p.x][p.y])/(double)v;
		int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
		for(int i=0;i<4;i++){
			int tempx=p.x+dx[i],tempy=p.y+dy[i];
			if(0<=tempx&&tempx<r&&0<=tempy&&tempy<c){
				if(!vis[tempx][tempy]){
					q.push(NODE(tempx,tempy,p.time+time)); //here
				}
			}
		}
	}

	//finalize
	if(NULL!=fin) fclose(fin);
	if(NULL!=fout) fclose(fout);

	return 0;
}

//WACODE
/*
TASK: PKU_3037 - Skiing
LANG: C++
NAME: untitled.cpp
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>

#define RMAX 100
#define CMAX 100

using namespace std;

struct NODE
{
	int x,y;
	double time;
	NODE(){};
	NODE(int _x,int _y,double _time)
	{
		x = _x; y = _y; time = _time;
	}
};
bool operator <(const NODE &left,const NODE &right)
{
	return left.time<right.time; //here
}

int table[RMAX][CMAX];
bool vis[RMAX][CMAX];

int main()
{
	FILE *fin=NULL,*fout=NULL;
	fin = freopen("input.txt","r",stdin);
	fout = freopen("output.txt","w",stdout);

	//Dijkstra。 O(RClog(RC))

	int v,r,c; scanf("%d%d%d",&v,&r,&c);
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			scanf("%d",table[i]+j);
			if(!(0==i&&0==j)){
				table[i][j] -= table[0][0];
			}
		}
	}
	table[0][0] = 0;

	priority_queue<NODE> q; q.push(NODE(0,0,0.0l));
	for(int i=0;i<r;i++){
		fill(vis[i],vis[i]+c,false);
	}
	while(!q.empty()){
		NODE p=q.top(); q.pop();
		if(vis[p.x][p.y]){
			continue;
		}

		vis[p.x][p.y] = true;
		if(r-1==p.x&&c-1==p.y){
			printf("%.2lf\n",-p.time); //here
			break;
		}

		double time=pow((double)2.0l,(double)table[p.x][p.y])/(double)v;
		int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
		for(int i=0;i<4;i++){
			int tempx=p.x+dx[i],tempy=p.y+dy[i];
			if(0<=tempx&&tempx<r&&0<=tempy&&tempy<c){
				if(!vis[tempx][tempy]){
					q.push(NODE(tempx,tempy,p.time-time)); //here
				}
			}
		}
	}

	//finalize
	if(NULL!=fin) fclose(fin);
	if(NULL!=fout) fclose(fout);

	return 0;
}

• 仔细看看 (76) 2125873653zzk 2018-03-31 11:29:04