We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #83: Path sum: four ways
  4. Discussions

Project Euler #83: Path sum: four ways

Sort by

recency

|

13 Discussions

|

  • fran_mahon
     + 0 comments

    C++

    #include <bits/stdc++.h>
using namespace std;

typedef pair<long long, long long> Cell;

int N;

pair<int, int> dir[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
vector<vector<long long>> grid;


long long Dijkstra()
{
    priority_queue<Cell, vector<Cell>, greater<Cell>> Q;                    
    
    vector<long long> cost((N * N) + 1, 1e15);
    vector<pair<int, int>> M(N * N + 1);
    
    cost[0] = 0;
    
    long long index = 0;
    
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {            
            M[index] = {i, j};
            index++;                        
        }
    }    
    Q.push({grid[0][0], 0});
    
    while(!Q.empty())
    {
        long long cell = Q.top().second;
        long long currCost = Q.top().first;         
     
        if(cell == N * N - 1) return currCost;
        
        Q.pop();
        
        int y = M[cell].first;
        int x = M[cell].second;

        for(auto d : dir)
        {
            int next_y = y + d.first;
            int next_x = x + d.second;
            
            if(next_y < 0 || next_x < 0 || next_y >= N || next_x >= N) continue;
            
            long long nextCost = currCost + grid[next_y][next_x];
            long long next_index = (next_y * N) + next_x;
            
            if(nextCost < cost[next_index])
            {
                cost[next_index] = nextCost;
                Q.push({nextCost, next_index});
            }
        }
    }
    return cost[N * N - 1];
}

int main() 
{
    cin >> N;
    grid.resize(N, vector<long long>(N));    
    
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            cin >> grid[i][j];
        }
    }
    long long ans = Dijkstra();

    cout << ans;
    return 0;
}

  • pradeexsu
     + 0 comments

    for C++ remove all log fector of searching in map mean's do not use map use 2d array of list of pair, int i got AC using 

    long long dist[701][701];
list<pair<pair<int,int>,int>> graph[701][701];

    use stl set c++ as priority queue.

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

  • JadedBeast
     + 0 comments

    I got TLE for using int instead of long long .

    Anyway learned a lot of tricks trying to solve this problem.

  • Anonympous
     + 0 comments

    @shashank21j why this solution give wrong answer for test cases 4 5 6 8:

    #include<bits/stdc++.h>
#include<stdio.h>
#include<limits.h>
using namespace std;
#define ROW 1001
#define COL 1001
typedef unsigned long long ull;
const long long M=1e9+7;
struct cell
{
    ull x, y;
    ull distance;
    cell(ull x, ull y, ull distance) :
        x(x), y(y), distance(distance) {}
};

bool operator<(const cell& a, const cell& b)
{
    if (a.distance == b.distance)
    {
        if (a.x != b.x)
            return (a.x < b.x);
        else
            return (a.y < b.y);
    }
    return (a.distance < b.distance);
}



ull shortest(ull grid[ROW][COL], ull row, ull col)
{
    ull dis[row][col];
    for (ull i = 0; i < row; i++)
        for (ull j = 0; j < col; j++)
            dis[i][j] = INT_MAX;
    int  dx[] = {-1, 0, 1, 0};
    int  dy[] = {0, 1, 0, -1};

    set<cell> st;
    st.insert(cell(0, 0, 0));
    dis[0][0] = grid[0][0];
    while (!st.empty())
    {
        cell k = *st.begin();
        st.erase(st.begin());
        for (ull i = 0; i < 4; i++)
        {
            ull x = k.x + dx[i];
            ull y = k.y + dy[i];
            if (!(x>=0 && x<=row-1 &&y>=0 && y<=col-1))
                continue;
            if (dis[x][y] > dis[k.x][k.y] + grid[x][y])
            {
                if (dis[x][y] != INT_MAX)
                    st.erase(st.find(cell(x, y, dis[x][y])));
                dis[x][y] = dis[k.x][k.y] + grid[x][y];
                st.insert(cell(x, y, dis[x][y]));
            }
        }
    }

    return dis[row - 1][col - 1];
}

int  main()
{
    ull n;
    cin >>n;
    ull cost[ROW][COL];
    for(ull i=0;i<n;i++)
    {
        for(ull j=0;j<n;j++)
        {
            cin >>cost[i][j];
        }
    }
    ull  ans=shortest(cost, n, n);
    cout<<ans;

return 0;
}