プロジェクトオイラー問83 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2083
Problem 83 「経路の和:4方向」 †
数字の書かれたマス目を上下左右に移動しながら左上から右下まで移動するとき経路和の最小値を求めよ。

解法
貪欲法で十分です。

#include<stdio.h>
#include<vector>
#include<queue>


struct E{
 	int x,y,sum;
	bool operator<(const E& e)const{
		return sum>e.sum;
	}
};

int main(){

	FILE *fp;
	char *fname = "pe81.txt";
	
	fp = fopen( fname, "r" );
	if( fp == NULL ){
		printf( "%sファイルが開けません\n", fname );
		return -1;
	}
	int n;
	char c;
	int row=0;
	std::vector<std::vector<int> > mat,memo;
	std::vector<int> vec;
	mat.push_back(vec);
	memo.push_back(vec);
	while(fscanf(fp,"%d%c",&n,&c)!=EOF){
		mat[row].push_back(n);
 		memo[row].push_back(-1);
		if(c=='\n'){
			mat.push_back(vec);
			memo.push_back(vec);
			row++;
		}
	}
	fclose(fp);
	int w=mat[0].size();
	int h=mat.size();
	std::priority_queue<E> pq;
	E e1,e2;
	e1.sum=mat[0][0];
	e1.x=e1.y=0;
	pq.push(e1);
	
	while(pq.empty()==false){
		e1=pq.top();
		pq.pop();
		if(e1.x==w-1&&e1.y==h-1){
			break;
		}
		int dxs[4]={0,1,0,-1};
		int dys[4]={1,0,-1,0};
		for(int i=0;i<4;i++){
			e2=e1;
			e2.x+=dxs[i];
			e2.y+=dys[i];
			if(e2.x>=w || e2.x<0 || e2.y>=h || e2.y<0)continue;
			e2.sum+=mat[e2.y][e2.x];
 			int num=memo[e2.y][e2.x];
			if(num==-1 || num>e2.sum){
				memo[e2.y][e2.x]=e2.sum;
				pq.push(e2);
			}
		}
 		
	}
	printf("%d\n",e1.sum);
}