You are viewing a single comment's thread. Return to all comments →
Can't be solvable by DP but by Dijkstra. My solution:
#include<bits/stdc++.h> #define ull unsigned long long using namespace std; bool is_valid(ull i,ull j,ull n){ if(i<0 || j<0 || i>=n || j>=n) return false; return true; } int main() { ull n; cin>>n; vector<vector<ull>> a(n, vector<ull>(n, 0)); for(ull i=0;i<n;i++) for(ull j=0;j<n;j++) cin>>a[i][j]; vector<pair<ull,ull> > adj[n*n+1]; for(ull i=0;i<n;i++){ for(ull j=0;j<n;j++){ if(is_valid(i,j-1,n))adj[i*n+j+1].push_back({a[i][j-1],i*n+j}); if(is_valid(i,j+1,n))adj[i*n+j+1].push_back({a[i][j+1],i*n+j+2}); if(is_valid(i-1,j,n))adj[i*n+j+1].push_back({a[i-1][j],(i-1)*n+j+1}); if(is_valid(i+1,j,n))adj[i*n+j+1].push_back({a[i+1][j],(i+1)*n+j+1}); } } priority_queue<pair<ull,ull>,vector<pair<ull,ull>>,greater<pair<ull,ull>> > pq; pq.push({a[0][0],1}); vector<bool> vis(n*n+1,false); vector<ull> dis(n*n+1,LONG_MAX); dis[1]=a[0][0]; while(!pq.empty()){ pair<ull,ull> x=pq.top(); dis[x.second]=x.first; vis[x.second] = true; pq.pop(); for( auto j:adj[x.second]){ if(!vis[j.second] && dis[j.second]>x.first+j.first){ dis[j.second]=dis[x.second]+j.first; pq.push({dis[j.second],j.second}); } } } cout<<dis[n*n]<<endl; return 0; }
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #83: Path sum: four ways
You are viewing a single comment's thread. Return to all comments →
Can't be solvable by DP but by Dijkstra. My solution: