# My Weblog

## 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.