# Shortest Paths with Non-Negative Edge Weights : Why did the cow cross the road?

My solution differs from the official. It passes task 1 and 10 only.
Differences:

• I denote edges as set of three edges.
So the edge weight is the value of the next grass field + 3*t

Then obviously to get to field (n-1, n-1) (0 -indexed) we must check all fields with Manhattan distance of 2 (1 or 2)

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> ii;

typedef vector<pair<int, int>> vii;

typedef vector vi;

typedef long long ll;

#define PB push_back

#define MP make_pair

#define FOR(i, x, y) for (int i = x; i < y ; i ++)

void IO(string s){

``````ios_base::sync_with_stdio(0); cin.tie(0);

freopen((s+".in").c_str(),"r",stdin);

freopen((s+".out").c_str(),"w",stdout);
``````

}

int n, t;

const int MAX_N = 101;

int val[MAX_N][MAX_N];

ll dist[MAX_N][MAX_N];

int visited[MAX_N][MAX_N];

//generates all possible groups of 3 edges that start at vertex (i,j)
void generate(int i, int j){

``````vii a = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}};

FOR(x, 0, 4){

int y = 3 - x;

for(auto pr : a){

int new_i = i + pr.first*x;

int new_j  =j + pr.second*y;

if (new_i >= 0 && new_j >= 0 && new_i < n && new_j < n){

}

}

}

for(auto pr : a){

int new_i = i + pr.first;

int new_j  =j + pr.second;

if (new_i >= 0 && new_j >= 0 && new_i < n && new_j < n){

}

}
``````

}

ll dijkstra(){

``````FOR(i, 0, MAX_N){

FOR(j, 0, MAX_N){

dist[i][j] = LLONG_MAX;

visited[i][j] = 0;

}

}

priority_queue<pair<ll, ii>> q;

q.push(MP(0, MP(0, 0)));

dist[0][0] = 0;

while(!q.empty()){

ii a = q.top().second;

q.pop();

if (visited[a.first][a.second]){

continue;

}

visited[a.first][a.second] = 1;

ll new_dist = dist[a.first][a.second] + val[next.first][next.second] + 3*t;

if (new_dist < dist[next.first][next.second]){

dist[next.first][next.second] = new_dist;

q.push(MP(-new_dist, next));

}

}

}

dist[n - 1][n - 1] = min(dist[n - 1][n - 1], t + dist[n - 1][n - 2]);

dist[n - 1][n - 1] = min(dist[n - 1][n - 1], t + dist[n - 2][n - 1]);

FOR(i, 0, 3){

int  j = 2 - i;

dist[n - 1][n - 1] = min(dist[n - 1][n - 1], dist[n - 1 -i][n- 1 - j] + 2 *t);

}

return dist[n - 1][n - 1];
``````

}

int main(){

``````IO("visitfj");

cin >> n >> t;

FOR(i, 0, n){

FOR(j, 0, n){

cin >> val[i][j];

generate(i, j);

}

}

cout << dijkstra() << '\n';
``````

}