CORONA - Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest - Division 3

Contest - Division 2

Contest - Division 1

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Dijkstra

PROBLEM:

There are N cities and M bidirectional roads. Each road has a particular cost to travel on.

K cities among these have corona testing facility for a particular amount (different cities may have different prices for testing).

Determine for each city, the minimum cost to travel to any corona testing facility and get tested.

EXPLANATION:

Model the problem as a weighted graph with N+1 nodes. Draw an edge between node 0 and node i with a corona testing facility (for all i), and give it weight C_i.

Now, we have reduced the problem to finding the shortest path from each city to node 0. This is equivalent to finding the shortest path from node 0 to each city, which is a classical Dijkstra problem!

TIME COMPLEXITY:

Dijkstra (with minimum priority queue) takes

O(V+E\log V)

which is the time complexity per test case.

SOLUTIONS:

Editorialist’s solution can be found here.

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

2

You don’t even have to add the extra node. It’s actually equivalent to performing Multisource Dijkstra

3 Likes
3

That is equivalent though and boils down to adding an imaginary vertix, the same way as multisource BFS. I’d still argue it’s much easier to understand when phrased this way, as it fits into the general idea, so you don’t have manually to skip some steps.

1 Like
4

can anybody explain why we need to drow the edge from 0 to ith node (which has corona vaccine)
actually we need to find the shortest path from the ith node + cost of vaccine
please explain so we nebie can also understand

5

Take it this way. There is a ‘super’ hospital at node 0. All hospitals don’t test the samples by themselves; instead they send the samples to this ‘super’ hospital (which tests it for free).

The distance from hospital i to node 0 is C_i (so the charges you pay for the testing is actually the charges you are paying the hospital to take the samples to hospital 0).
Now, instead of giving the hospital your sample and paying them to send it to hospital 0, why don’t you go yourself to hospital 0 and get your testing done for free? The total cost incurred is the same, in both cases.

That is exactly what the editorial solution does. Let me know if this isn’t clear.

5 Likes
6

thansk man this make more sence
insted of going to intermediate nearest hospital assume vaccine cost as traviling cost to the ‘super’
hospital , then problem trun’s to the find the shortes path from each node to the super hospital

7

where is the link to the code?

8

Sorry, has been fixed now!

9

Or we can also use the vertex with minimum C_i as source because optimal strategy for this vertex will be to stay in the city itself. So we can find shortest path from this city to every other as well.

My Submission

10

Can anyone please tell me what’s the problem with my code. HELP NEEDED !!!

public static void main (String[] args) throws java.lang.Exception
{

    in = new FastReader();
    out = new PrintWriter(System.out);
	int t = ni();
	while(t-- > 0){
	    long n = nl();
	    long m = nl();
	    long k = nl();
	    long[] hospital = new long[(int)(n)];
	    
	    Arrays.fill(hospital, Integer.MAX_VALUE);
	    
	    for(int i = 0; i < k; i++){
	        long idx = nl() - 1;
	        hospital[(int)(idx)] = nl();
	    }
	    
	    long[][] distance = new long[(int)(m)][3];
	    
	    for(int i = 0; i < (int)(m); i++){
	        distance[i][0] = nl();
	        distance[i][1] = nl();
	        distance[i][2] = nl();
	    }
	    
        minCost(n, hospital, distance);
	    
	    
	}
}


public static void minCost(long n, long[] hospital, long[][] testing){
    
    ArrayList<ArrayList<Pair>> graph = new ArrayList<>();
	    
    for(long i = 0; i <= n; i++){
        graph.add(new ArrayList<>());
    }
    
    for(int i = 0; i < testing.length; i++){
        long u = testing[i][0];
        long v = testing[i][1];
        long wt = testing[i][2];
        
        graph.get((int)(u)).add(new Pair(v, wt + hospital[(int)(u - 1)]));
        graph.get((int)(v)).add(new Pair(u, wt + hospital[(int)(v - 1)]));
    }
    
    for(int i = 1; i <= n; i++){
        graph.get(0).add(new Pair(i, hospital[i - 1]));
        graph.get(i).add(new Pair(0, hospital[i - 1]));
    }
    
    PriorityQueue<Pair> pq = new PriorityQueue<>();
    
    boolean[] visited = new boolean[(int)(n + 1)];
    long[] ans = new long[(int)(n + 1)];
    ArrayList<Pair> list = graph.get(0);
    for(Pair nbr: list){
        pq.add(nbr);
    }
    
    while(pq.size() > 0){
        Pair rem = pq.remove();
        
        if(visited[(int)(rem.nbr)]) continue;
        
        ans[(int)(rem.nbr)] = rem.wt;
        visited[(int)(rem.nbr)] = true;
        
        ArrayList<Pair> nbrs = graph.get((int)(rem.nbr));
        for(Pair vtx: nbrs){
            if(!visited[(int)(vtx.nbr)]) pq.add(vtx);
        }
    }
    
    for(int i = 1; i <= n; i++){
        System.out.print(ans[i] + " ");
    }
    
    System.out.println();
    
}
11

Please Help me with this @infinitepro

12

There is a problem called Water distribution problem , you can look it up , it’s approach is VERY VERY similar to the approach used in this problem
In that problem you need to calculate minimum cost to supply water to all plants , since you need to supply water to all plants what you do is you create a dummy node 0 and apply MST algorithm
But here you need to find minimum cost for each node of the graph , which is similar to to finding shortest path , so u use dijkstra

CONCLUSION : in future if we see a problem with something along the lines of :
some graph is given , centres are given , node to node cost is given (which is positive)
finding total cost to connect everything : dummy node + MST
finding min cost for each node : dummy node + dijkstra

13

I’m sorry, I don’t know java.
I believe some kind soul will help you, if you format your code (or give a link to your submission).

14

One problem I could see is your declaration of ArrayList, but there could possibly be more issues. So instead of writing:

ArrayList<ArrayList<Pair>> graph = new ArrayList<>();

Change it to:

ArrayList<ArrayList<Pair>> graph = new ArrayList<ArrayList<Pair>>();

BTW: I’m no pro at Java, so I don’t know if error code even compiles, but this sounds logical to me.

15

What’s the error you’re facing?
WA?
TLE?
RTE?

16

Actually there is no problem with declaration as I have solved the water distribution problem which is similar to this question.

17

WA error.
All the sample test cases are passed whereas hidden test cases show WA.

19

Some comments above show you are supposed to use Multi-Source Dijkstra’s algorithm. Is that what you are doing?

May be, put some comments along with statements to explain what you’re doing. It may help.

20

This code goes wa on half the test cases and ac on the other half. no idea what I am doing wrong.
please help.

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <string>
#include <unordered_map>
#include <climits>
#define deb(x) cout << #x << " "<<  x << endl;
using namespace std;
typedef unsigned long long ll;
typedef pair<ll,ll> pii;
typedef vector<pii> vpii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef map<char,int> mc;
typedef unordered_map<int,int> mi;
const int M = 1e9+7;

class Graph {
	private:
	ll nodes;
	list<pii> *adjlist;
	public:
	Graph(ll v) {
		nodes=v;
		adjlist = new list<pii>[v];
	}
	void addEdge(ll a,ll b,ll d) {
		adjlist[a].push_back({d,b});
		adjlist[b].push_back({d,a});
	}
	vi djikstra(int src) {
	   vi dist(nodes,INT_MAX);
	   set<pii> curr_nodes;
	   dist[src] = 0;
	   curr_nodes.insert({0,src});
	   while(!curr_nodes.empty()) {
	   		pii top = *curr_nodes.begin();
	   		curr_nodes.erase(curr_nodes.begin());

	   		ll curr_node = top.second;
	   		for(auto [dist_to_adjnode,adj_node]:adjlist[curr_node]){
	   			if(dist[curr_node] + dist_to_adjnode < dist[adj_node]) {
	   				if(dist[adj_node] != INT_MAX) {
	   					curr_nodes.erase(curr_nodes.find({dist[adj_node],adj_node}));
	   				}
	   				dist[adj_node] = dist[curr_node] + dist_to_adjnode;
	   				curr_nodes.insert({dist[adj_node],adj_node});	
	   			}
	   		}
	   }
	   return dist;	
	}
	~Graph() {
		delete []adjlist;
	}
};
void solve() {
	ll n,m,k;
	cin >> n >> m >> k;
	Graph g(n+1);
	for(ll i=0;i<k;i++) {
		ll x,c;
		cin >> x >> c;
		g.addEdge(0,x,c);
	}		
	for(ll i=0;i<m;i++) {
		ll a,b,d;
		cin >> a >> b >> d;
		g.addEdge(a,b,d);
	}
	vi dist = g.djikstra(0);
	for(auto i:dist)
		if(i!=0)
			cout << i << " ";
	cout << endl;
}
int main() {
	freopen("input.txt","r",stdin);
	int tc=1;
	cin >> tc;
	while(tc--)
		solve();
	return 0;
}
21

I guess #define int long long will solve the issue, but you can always manually change every int for long long inside your code. It’s because you get possible overflow due to the limits on edge lengths, so you exceed maximum integer value. Also, you shouldn’t set distances to INT_MAX, but to 10^{15} or more, because the longest path could possibly be 2 \cdot 10^5 \cdot 10^9 long.