poj 3037 (최 단 로)

제목:
Bessie 는 row * col 의 사각형 구역 에서 스키 를 타 는데 출발점 은 왼쪽 상단 이 고 초기 속도 v 를 알 고 있 습 니 다. a 시 에서 b 시 까지 속 도 는 v (a) * 2 ^ (A - B) (A, B 는 대응 점 의 높이) 로 바 뀌 었 습 니 다. a 에서 b 까지 걸 리 는 시간 은 a 의 속도 의 역수 입 니 다. 그녀 는 앞 뒤 좌우 네 방향 으로 이동 하여 오른쪽 아래 까지 의 최소 시간 을 구 할 수 있 습 니 다.
분석:
각 점 의 속 도 는 고정 적 이다. 예 를 들 어 a - > b - > c;그러면 c 출발 속 도 는 V * 2 ^ (A - B) * 2 ^ (B - C) = V * 2 ^ (A - C) 이 고 시간 은 속도 의 역수 이다.
주의:
1. inf 는 충분히 커 야 합 니 다.
2. 행렬 안의 값 범위 [- 25, 25] 때문에 1 < x 의 방식 으로 2 의 멱 을 구한다 면 이 수 는 전체 범위 가 범 위 를 초과 할 것 이 분명 하 다. 따라서   __int64 을 사용 해 야 한다.  t=1;

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstring>

 4 #include <algorithm>

 5 #include <cmath>

 6 #include <queue>

 7 

 8 using namespace std;

 9 

10 #define inf 99999999999LL

11 int dx[]={0,0,-1,1};

12 int dy[]={-1,1,0,0};

13 

14 struct point 

15 {

16     int x;

17     int y;

18 };

19 

20 double dis[103][103];

21 int map[103][103];

22 bool vis[103][103];

23 int V,R,C;

24 

25 

26 bool isok(point po)

27 {

28     if(po.x>0 && po.x<=R && po.y>0 && po.y<=C)

29         return true;

30     return false;

31 }

32 

33 void spfa(int r,int c,int v)

34 {

35     queue <point> Q;

36     __int64 t=1;

37     double k;

38     dis[1][1]=0;

39     point p={1,1};

40     Q.push(p);

41     vis[1][1]=1;

42     while(!Q.empty())

43     {

44         p=Q.front();

45         Q.pop();

46         vis[p.x][p.y]=0;

47         int s=map[1][1]-map[p.x][p.y];

48         if(s>=0)

49             k=(t<<s)*v;

50         else

51             k=1.0/(t<<(-s))*v;

52         for(int i=0;i<4;i++)

53         {

54             point next;

55             next.x=p.x+dx[i];

56             next.y=p.y+dy[i];

57             if(isok(next))

58             {

59                 if(dis[next.x][next.y] > dis[p.x][p.y] + 1.0/k)

60                 {

61                     dis[next.x][next.y] = dis[p.x][p.y] + 1.0/k;

62                     if(!vis[next.x][next.y])

63                     {

64                         vis[next.x][next.y]=1;

65                         Q.push(next);

66                     }

67                 }

68             }

69         }

70     }

71 }

72 

73 int main()

74 {

75     while(scanf("%d%d%d",&V,&R,&C) != EOF)

76     {

77         memset(vis,0,sizeof(vis));

78         for(int i=1;i<=R;i++)

79             for(int j=1;j<=C;j++)

80             {

81                 scanf("%d",&map[i][j]);

82                 dis[i][j]=inf;

83             }

84         spfa(R,C,V);

85         printf("%.2f
",dis[R][C]);

86         

87     }

88     return 0;

89 }