Project Euler #83: Path sum: four ways

  • + 0 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;
          }