EPATHS - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest

Author: Sumukh Bhardwaj
Tester: Rahul Sharma
Editorialist: Sumukh Bhardwaj

DIFFICULTY:

MEDIUM

PREREQUISITES:

DFS, DP, DIJKSTRA

PROBLEM:

Given N nodes with their values, find the number of paths between 0th and N-1th such that the values of nodes in the path are in decreasing order.

QUICK EXPLANATION:

Traverse all the paths using DFS and memoize the DFS recursion to fasten up the algorithm.

EXPLANATION:

Subtask #1:

Recursion without Memoization

  • Use Dijkstra to find out the elevation of all the nodes.
  • To find out all the paths from 0th and N-1th with the given constraints, start a DFS from 0th node and traverse to only those adjacent nodes whose elevation is lesser than this node.
  • If we reach the N-1th node then we have completed a path. Add all these paths and return it modulo 10^9 + 7.

Subtask #2:

Recursion with Memoization

  • The only optimization required to pass the second subtask is to store the number of paths starting with the ith node. When we revisit a node then instead of calculating the number paths again extract it from the table.

COMPLEXITIES

For all subtasks to pass

TIme Complexity:
Preprocessing - O(M * logN) , where M is number of edges, N is number of nodes

Space Complexity: O(M + N)

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;

const long long N = 1e5, mod = 1e9+7;

void dijkstra(long long dis[], vector<pair<long long, long long>> adj[], long long src, long long n) {
    long long v,d;

    for (long long i = 0; i < n; i++)
        dis[i] = 1e18;
    dis[src] = 0;

    priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;

    pq.push({0, src});

    while(pq.empty()==0) {
        pair<long long, long long> p = pq.top();
        pq.pop();

        v = p.second; d = p.first;

        for (long long i = 0; i < adj[v].size(); i++) {
            if (dis[adj[v][i].first] > d + adj[v][i].second) {
                dis[adj[v][i].first] = d + adj[v][i].second;
                pq.push({dis[adj[v][i].first], adj[v][i].first});
            }
        }
    }
}

long long dfs(long long dp[], long long dis[], vector<pair<long long, long long>> adj[], long long src,long long dest) {
    if(src==dest)
        return 1;

    if(dp[src]!=-1)
        return dp[src];

    long long ans = 0;
    for(long long i = 0; i < adj[src].size(); i++) {
        if (dis[adj[src][i].first] < dis[src])
            ans = (ans%mod + dfs(dp, dis, adj, adj[src][i].first,dest)%mod)%mod;
    }

    return dp[src]=ans%mod;
}

long long solve(long long n, vector<vector<long long>>& edges) {
    long long dp[N], dis[N];
    memset(dp, -1, sizeof(dp));
    vector<pair<long long, long long>>adj[n];

    for (long long i = 0; i < edges.size(); i++) {
        long long k1 = edges[i][0];
        long long k2 = edges[i][1];
        long long k3 = edges[i][2];

        adj[k1].push_back({k2,k3});
        adj[k2].push_back({k1,k3});
    }

    dijkstra(dis, adj, n-1, n);
    return dfs(dp, dis, adj, 0, n-1);
}

int main() {
    ios_base::sync_with_stdio(false);

    long long t, n, e, u, v, w;

    cin>>t;

    while(t--) {
        vector<vector<long long>> edges;
        cin>>n>>e;

        for (long long i = 0; i < e; i++) {
            cin >> u >> v >> w;
            edges.push_back({u, v, w});
        }

        cout<< solve(n, edges) <<endl;
    }
    return 0;
}
2 Likes