Dijkstra C++
ふいー
本読んだりして色々調べたけど、理論はわかってるわけだから、やっぱり自分で考えた方が早いや!!
と思って書いてみた。
少し長いので一番最後に載せる。
KUPCの確かB問題だったかな。
H行W列の0〜9の数字列が与えられ、 右方向または下方向にしか進まないという条件で、 一番左上から一番右下までの合計コストが最小となるそのコストを答えよ
時間が思うようにとれずに1週間近くブランクがあいてしまった。
さ、これをいよいよHaskellに落とし込む☆
どうやろうか。モナドを使うと楽な気がするんだけどなー
#include<iostream> #include<string> #define MAX 100000 #define N 1000 #define MIN(a,b) ((a)<(b) ? (a) : (b)) using namespace std; class Dijkstra{ int i,j,W,H,map[N][N]; int d[N][N]; //始点から接点までの距離 public: Dijkstra(){ for(i = 0 ; i < N ; i++) for(j = 0 ; j < N ; j++) d[i][j] = MAX; } void RoutSet(){ string input; cin >> H >> W; for(i = 0 ; i < H ; i++){ cin >> input; for(j = 0 ; j < W ; j++) map[i][j] = input[j] - '0'; } } int MinRout(){ for(i = 0 ; i < H ; i++){ for(j = 0 ; j < W ; j ++) d[i][j] = MIN(d[i][j] , map[i][j] + checkNext(i,j)); } return d[H-1][W-1]; } private: int checkNext(int x, int y){ int min = MAX; if(x == 0 && y == 0) return 0; if(x-1 >= 0 && min > d[x-1][y]) min = d[x-1][y]; if(y-1 >= 0 && min > d[x-1][y]) min = d[x][y-1]; return min; } };