kassutta's blog

Graph problem — Sprinklr coding test problem HELP!
By kassutta, history, 4 years ago, In English

UPDATE: CONTEST IS OVER MANY DAYS AGO DOWNVOTERS SO PLEASE!

You are given road network with N cities and M bi-directional roads. Each road has some positive amount of tax associated to it, meaning if there is a road connecting cities A and B with tax C, you will need to pay C rupees to the government every time when you use this road, but you have a wildcard which can be used at most K times and when you are using this wildcard while using the road, you do not need to pay tax associated to road. You are planning to visit one city this weekend, due to limited budget you want to estimate minimum possible cost from your home-city to every other city , so that you can choose the destination according to the budget. Your home-city is a city numbered with 1.

Input Format: First line of input contains N,M and K following M lines contains 3 integer U V C , meaning there is a road between cities U and V with tax associated.

Output Format: Print N space separated integers in a single line, ith integer indicating the minimum cost of travelling from city 1 to i.

Sample Input 4 4 1 1 2 2 2 3 3 1 3 6 3 4 11

Sample Output 0 0 0 5

  • Vote: I like it
  • -12
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by kassutta (previous revision, new revision, compare).

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

Auto comment: topic has been updated by kassutta (previous revision, new revision, compare).

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

What are the constraints, bbruh?

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

    constraints were not mentioned there , i was having this problem, so any solution that comes to ur mind u can share

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

Exactly the same Problem: https://www.hackerearth.com/practice/algorithms/graphs/shortest-path-algorithms/practice-problems/algorithm/shortest-path-revisited-9e1091ea/

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

    Yes thank you very much now i can solve it with given constraints and refer to the editorial

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

Just curious, does using a dfs, with passing all the path weights/taxes in a priority queue will work?

The only shortcoming I can think of is I might use a lot of memory, which might cause MLE for large test cases.

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

    yes this is a kind of brute force can work depends on constraints.

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

Using priority queue to store each value he has to pay and a normal bfs will work and then discarding initial k values from each if they exist.

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

    ya kind of, Dijksta using priority queue will work with Dp.

    → Reply