kickbust13's blog

k skip shortest path.
By kickbust13, history, 4 years ago, In English

can anyone help in solving the following question.

consider a weighted undirected graph. There is a source S and destination D and a value K. Find the length of the shortest path such that you can make at most K edges 0.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

We can create a graph with $$$k$$$ layers — lets call it $$$G[n][k]$$$. For each edge $$$(v,u,w)$$$ we add two types of edges to our graph:

  • $$$G[v][i]$$$ — $$$G[u][i]$$$ with weight $$$w$$$ (standard edge, needs to be in each layer)

  • $$$G[v][i]$$$ — $$$G[u][i+1]$$$ with weight $$$0$$$ ("skipping" edge, also in each layer)

Now if we calculate minimum distances to each vertex in the whole graph, distance to $$$G[v][l]$$$ will mean minimum distance to vertex $$$v$$$ if we made exactly $$$l$$$ edges to be equal 0.

If the weights are positive we can use Dijkstra's algorithm to calculate minimum distances giving us $$$O(nk*log(nk))$$$ complexity.

If weights can be negative we use Bellman–Ford algorithm giving us $$$O(n^2k^2)$$$ comlpexity.

Note that we need to take minimum distance to $$$d$$$ in all layers in order to find the answer (we "skip" at most $$$k$$$ edges)

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why we need to take minimum in all layers , should n't the minimum should be when you have skipped k edges . i.e G[dest][k] ??

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Because you can skip at most $$$k$$$ edges. It's unnecessary for positive weights, but for negative weights can result in wrong answers.

      → Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did anyone here implement his method? If yes, can you post the implementation?

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
      #include <bits/stdc++.h>
using namespace std;

// https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,s,e) for(int i=s ; i < e ; i++)
#define rrep(i,s,e) for(int i=s ; i > e ; i--)
#define srep(i,s,e,j) for(int i=s ; i < e ; i+=j)
#define tr(i,x) for(auto i : x)
#define vinp(a) for(int i=0 ; i<a.size() ; i++)cin>>a[i]
#define ainp(a,n) for(int i=0; i<n; i++)cin>>a[i]
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define vs vector<string>
#define vb vector<bool>
#define vpi vector<pii>
#define maxpqi priority_queue<int>
#define minpqi priority_queue <int, vector<int>, greater<int> >
#define mem0(x) memset(x, 0, sizeof(x))
#define mem1(x) memset(x, -1, sizeof(x))
#define pii pair<int,int> 
#define F first
#define S second
#define mk make_pair
#define pb push_back
#define pf push_front
#define endl '\n'
#define gcd(a,b) __gcd(a,b)
#define clr(x) memset(x,0,sizeof(x))
#define lb lower_bound
#define ub upper_bound
#define npos string::npos
#define all(x) x.begin(),x.end()
#define sayyes cout << "YES" << endl
#define sayno cout << "NO" << endl

struct Node{
    int v, k, d;
    Node(){
        v = k = d = 0;
    }
    Node(int _v, int _k, int _d){
        v = _v,k = _k,d = _d;
    }
};
typedef struct Node Node;

class Compare{
public:
    bool operator()(const Node& a, const Node& b){
        // min priority queue according to dist
        return  a.d > b.d;
    }
};

vector<vpi>adj;
vvi dp;
int n, K;

void dijkstra(int src){
    dp[src][0] = 0; // distance from src to src after using 0 coupon is 0
    priority_queue<Node, vector<Node>, Compare>pq;
    pq.push(Node(src, 0, 0));
    
    Node tp;
    int from, k, dist;
    int to, edgew;
    while(!pq.empty()){
        tp = pq.top(); pq.pop();
        from = tp.v, k = tp.k, dist = tp.d;
        if(dp[from][k] < dist) continue;

        for(auto p: adj[from]){
            to = p.F, edgew = p.S;
            if(dist + edgew < dp[to][k]){
                dp[to][k] = dist + edgew;
                pq.push(Node(to, k, dp[to][k]));
            }   


            if(k+1 <= K && dist < dp[to][k+1]){
                dp[to][k+1] = dist;
                pq.push(Node(to, k+1, dp[to][k+1]));
            }
        }
    }
}

void solve(){
    int m; cin >> n >> m >> K;
    // K = 1; // max number of edges on which discount can be used.


    adj.assign(n+1, vpi());
    int u, v, w;
    rep(i, 0, m){
        cin >> u >> v >> w;
        adj[u].pb({v, w});
    }

    dp.assign(n+1, vi(K+1, LONG_MAX));
    // ```dp[i][k] denote minimum distance from 1 to i after using discount coupon on k edges```

    dijkstra(1);
    
    int ans = LONG_MAX;
    rep(j, 0, K) ans = min(ans, dp[n][j]);

    cout << ans << endl;
}

int32_t main(){
    fastio
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--){
        solve();
        // cout << solve() << endl;
        // cout << (solve() ? "yes" : "no") << endl;
    }
    return 0;
}
      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone give link to problem of this type on codeforces

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

CODE with explanation void findMinDistance(vector<pair<int, int>> adj[], int N, int k) { // {dist, {node, leftout}} priority_queue<pair<int, pair<int, int>>> pq; pq.push({0, {1, 0}});

int dist[N + 1][k + 1];
for (int i = 0; i <= N; i++)
{
    for (int j = 0; j <= K; j++)
    {
        if (i == 0)
            dp[i][j] = 0;
        else
            dp[i][j] = INT_MAX;
    }
}

while (!pq.empty())
{
    // it -> {dist, {node, leftout}}
    auto it = pq.top();
    pq.pop();

    int node = it.second.first;
    int x = it.second.second;
    int dis = dist[node][x]; // it.first

    // iterate over all adjacent nodes
    for (auto iter : adj[node])
    {
        int y = iter.first;
        int d = iter.secoond;

        // at first lets do without leaving out any edges
        if (dis + d < dist[y][x])
        {
            dist[y][x] = dis + d;
            // pq is max heap, but i need minimal distance at top
            // so to make sure the max heap is used as
            // min heap, i converted it by having negatives, so
            // that max heap works in opposite
            pq.push({-1 * (dis + d), {y, x}}); // why did i take -1 ?
        }
        // if the max turn off edges have been done,
        // no need to further turn off edges
        if (x == k)
            continue;

        if (dis < dist[y][x + 1])
        {
            dist[y][x + 1] = dis;
            // pq is max heap, but i need minimal distance at top
            // so to make sure the max heap is used as
            // min heap, i converted it by having negatives, so
            // that max heap works in opposite
            pq.push({-1 * (dis), {y, x + 1}}); // why did i take -1 ?
        }
    }
}
int mini = INT_MAX;
// in reaching N, you can take any dist
// by turning of 0, 1, 2, 3, 4, 5,... edges

for (int i = 0; i <= k; i++)
    mini = min(mini, dist[N][i]);
return mini;

}

→ Reply