My Weblog

Blog about programming and math

Project Euler problem 82

Project Euler problem 82 is simple Dijkstra exercise and test your STL implementation skills. Easy problem.

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
typedef long long ll;
ll  M[100][100],dx[4]={0,1,0,-1},dy[4]={1,0,-1,0},m;
bool vis[100][100];
struct state 
	{
		ll x,y,cost;
		bool operator <(state s)const 
		{
			return this->cost>s.cost;
		}
	};

bool check(ll x,ll y)
	{

		if (x<0 || x>=m || y<0 ||y>=m || vis[x][y]) return 1;
		return 0;
	}

int main()
	{
		ll k,ret=1LL<<40;
		cin>>m;
		for(int i=0;i<m;i++)for(int j=0;j<m;j++)cin>>k,M[i][j]=k;
		for(int i=0;i<m;i++)
		{
			memset(vis,0,sizeof vis);
			priority_queue<state> Q;
			Q.push((state){i,0,M[i][0]});//x,y,cost
			while(!Q.empty())
			{
				state t=Q.top();Q.pop();
				if(t.y==(m-1)) { ret=min(ret,t.cost);break;}
				if(vis[t.x][t.y]) continue; 
				vis[t.x][t.y]=1;
				for(int i=0;i<4;i++)
				{
					if (check(t.x+dx[i],t.y+dy[i])) continue;
					Q.push((state){t.x+dx[i],t.y+dy[i],t.cost+M[t.x+dx[i]][t.y+dy[i]]});
					
				}
				
			}
		}
		cout<<ret<<endl;
	}
Advertisements

July 24, 2010 - Posted by | Programming

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: