Landline Telephone Network

Introduction

This asks you to connect n (1000) nodes with minimum cost such that some given "insecure" nodes are leaf nodes in the spanning graph.

Solutions

MST

Without the "insecure" nodes, the problem is literally asking for the minimum spanning tree. With insecure nodes, we know they must be leaves, so we can simply connect them one at a time to the MST with whatever the lowest cost edge between the insecure node and any secure node.

Gotchas

• All points might be insecure, so there is no MST. have to check instead whether graph is fully connected
• The graph of secure nodes may be disconnected, making the answer "impossible"
• An insecure node may have no connection to a secure node making the answer "impossible"

Code

Solution - Java

import java.awt.Point;
import java.util.*;
public class f {
	Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		new f().go();
	}
	private void go() {
		int n=in.nextInt(),m=in.nextInt(),p=in.nextInt();
		ArrayList<HashMap<Integer,Integer>> al=new ArrayList<HashMap<Integer,Integer>>();
		for(int i=0;i<n+1;i++)al.add(new HashMap<Integer,Integer>());
		HashSet<Integer> is=new HashSet<Integer>();
		for(int i=0;i<p;i++)is.add(in.nextInt());
		for(int i=0;i<m;i++){
			int x=in.nextInt(),y=in.nextInt(),l=in.nextInt();
			al.get(x).put(y, l);
			al.get(y).put(x, l);
		}
		ArrayList<Point> mst = MST2(al,is);
		int ans=0;
		for(Point ps:mst)ans+=al.get(ps.x).get(ps.y);
		if(p==n){//every city is insecure...must be fully connected
			for(int i=1;i<n;i++)for(int j=i+1;j<=n;j++){
				if(!al.get(i).containsKey(j)){
					System.out.println("impossible");
					System.exit(0);
				}
				ans+=al.get(i).get(j);
			}
		} else {//some node is in the MST....must take cheapest link
			for(int i:is){
				int min=Integer.MAX_VALUE;
				for(int j:al.get(i).keySet())if(!is.contains(j))min=Math.min(min, al.get(i).get(j));
				if(min==Integer.MAX_VALUE){//no link to MST.
					System.out.println("impossible");
					System.exit(0);
				}
				ans+=min;
			}
		}
		System.out.println(ans);
	}
	public ArrayList<Point> MST2(ArrayList<HashMap<Integer,Integer>> in,HashSet<Integer>is){
		ArrayList<Point> out=new ArrayList<Point>();
		HashSet<Integer> visited=new HashSet<Integer>(is);
		final ArrayList<HashMap<Integer,Integer>> al=new ArrayList<HashMap<Integer,Integer>>(in);
		PriorityQueue<Point> pq=new PriorityQueue<Point>(al.size(), new Comparator<Point>(){
			public int compare(Point o1, Point o2) {
				double d=al.get(o1.x).get(o1.y)-al.get(o2.x).get(o2.y);
				if(d!=0)return (int) Math.signum(d);
				if(o1.x!=o2.x)return o1.x-o2.x;
				return o1.y-o2.y;
			}
		});
		int first=1;
		while(visited.contains(first))first++;
		visited.add(0);
		visited.add(first);
		if(first>=al.size())return out;//all points are insecure...no MST
		for(int i:in.get(first).keySet())pq.offer(new Point(first,i));
		while(!pq.isEmpty()){
			Point t=pq.poll();
			if(visited.contains(t.y))continue;
			visited.add(t.y);
			out.add(t);
			for(int i:in.get(t.y).keySet())	if(!visited.contains(i))pq.offer((new Point(t.y,i)));
		}
		if(visited.size()!=al.size()){//graph is disconnected
			System.out.println("impossible");
			System.exit(0);
		}
		return out;
	}
}