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

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2082
Problem 82 「経路の和:3方向」 †
数字の書かれたマス目を上下右に移動しながら左から右へ移動するとき経路の数字の和を最小にする移動経路をとった時の和を答えよ。

解法
貪欲法で十分です。

#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;
 	for(int i=0;i<h;i++){
		e1.x=0;
		e1.y=i;
		e1.sum=mat[i][0];
	pq.push(e1);
	}
	while(pq.empty()==false){
		e1=pq.top();
		pq.pop();
		if(e1.x==w-1){
			break;
		}
		int dxs[3]={0,1,0};
		int dys[3]={1,0,-1};
		for(int i=0;i<3;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);
}