## 11631 - Dark roads

All about problems in Volume 116. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

### 11631 - Dark roads. WA!!!

Hi,

I believe I chose right approach, but I got WA,
Could anybody help with advice or provide some input

Code: Select all

``````import java.io.*;
import java.util.Arrays;
import java.util.Scanner;

class Main {

public static void main(String[] args) {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

try {
Scanner scanner = new Scanner(reader);

while (scanner.hasNextInt()) {

int m = scanner.nextInt();
int n = scanner.nextInt();

Distance[] distances = new Distance[n];
int sum = 0;
for (int i = 0; i < n; i++) {
int from = scanner.nextInt();
int to = scanner.nextInt();
int distance = scanner.nextInt();
distances[i] = new Distance(from, to, distance);
sum += distance;
}

WeightedQuickUnion quickUnion = new WeightedQuickUnion(m + 1);

Arrays.sort(distances);

int totalDistance = 0;

for (Distance distance : distances) {

if (quickUnion.find(distance.from, distance.to)) {
continue;
}

totalDistance += distance.distance;

quickUnion.union(distance.from, distance.to);

}

writer.write((sum-totalDistance) + "\n");

}

writer.flush();
} catch (IOException e) {
e.printStackTrace();
}
}

static class Distance implements Comparable<Distance> {
int from, to, distance;

Distance(int from, int to, int distance) {
this.from = from;
this.to = to;
this.distance = distance;
}

@Override
public int compareTo(Distance o) {
int distanceDiff = distance - o.distance;

if (distanceDiff != 0) {
return distanceDiff;
}

int fromDiff = from - o.from;
if (fromDiff != 0) {
return fromDiff;
}

return to - o.to;

}
}

static class QuickUnion extends FindUnion {
public QuickUnion(int n) {
super(n);
}

@Override
public void union(int p, int q) {
int i = getRoot(p);
int j = getRoot(q);
array[i] = j;
groups--;
}

@Override
public boolean find(int a, int b) {
return getRoot(a) == getRoot(b);
}

protected int getRoot(int a) {

if (a == array[a]) {
return a;
}
return getRoot(array[a]);
}
}

static abstract class FindUnion {

protected final int[] array;
protected int groups;

protected FindUnion(int n) {
this.array = new int[n];
for (int i = 1; i < array.length; i++) {
array[i] = i;
}
groups = n;
}

public abstract void union(int p, int q);

public abstract boolean find(int p, int q);

public int getGroups() {
return groups;
}
}

static class WeightedQuickUnion extends QuickUnion {
final int[] size;
public WeightedQuickUnion(int n) {
super(n);
size = new int[n];
for (int i = 0; i < size.length; i++) {
size[i] = 1;
}
}

@Override
public void union(int p, int q) {
int i = getRoot(p);
int j = getRoot(q);

if (size[i] < size[j]) {
array[i] = j;
size[j] += size[i];
} else {
array[j] = i;
size[i] += size[j];
}
groups--;

}
}
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11631 - Dark roads. WA!!!

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

laituanksa245
New poster
Posts: 20
Joined: Tue Jan 10, 2012 4:23 pm
Location: Vietnam

### 11631 - Dark roads

I kept getting TLE on this problem.
Any suggestion to speed up my program ?
I used Kruskal algorithm.

Code: Select all

``````Code Removed.
Got AC
``````
Last edited by laituanksa245 on Sun Jan 06, 2013 6:12 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11631 - Dark roads TLE

Add union find to Kruskal's algorithm.
Check input and AC output for thousands of problems on uDebug!

laituanksa245
New poster
Posts: 20
Joined: Tue Jan 10, 2012 4:23 pm
Location: Vietnam

### Re: 11631 - Dark roads TLE

Thanks very much. Got AC Saminur Islam
New poster
Posts: 4
Joined: Tue Dec 10, 2013 10:49 am

### Re: 11631 - Dark roads TLE

I think this is a simple mst problem I use prim algorithm but getting submission error ..... plz help me to find out the problem in my code

Code: Select all

``````#include<iostream>
#include<vector>
#include<map>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<set>
#include<list>
#include<utility>
#include<fstream>
#include<cmath>
using namespace std;

int M,N;
vector<pair<int,int> >node;
bool visited;
int dist;
int parent;
int minkey()
{
int i,min;
for(i=0;i<M;i++)
{
if(visited[i]==false)
{
min=i;
break;
}
}
for(i=0;i<M;i++)
{
if(dist[min]>dist[i] && visited[i]==false) min=i;
}
return min;
}

void prim()
{
int i,j;
int k,distance;
int value;
memset(visited,false,sizeof visited);
memset(parent,-1,sizeof parent);
for(int i=0;i<M;i++)dist[i]=1000000;
dist=0;
i=0;
for(i=0;i<M;i++)
{
int min= minkey();
visited[min]=true;
//cout<<min<<" "<<dist[min]<<endl;
for(j=0;j<node[min].size();j++)
{
pair<int,int>p;
p=node[min][j];
value=p.first;
distance=p.second;
if(visited[value]==false && distance<dist[value])
{
dist[value]=distance;
parent[value]=min;

}
}
}
}

int main()
{
//freopen("i.txt","r",stdin);
int i,j,k;
int totalcost2;
int value1,value2,weight;
while(scanf("%d %d",&M,&N)==2)
{
if(M==0&&N==0) break;
totalcost2=0;
for(i=0;i<N;i++)
{
scanf("%d %d %d",&value1,&value2,&weight);
totalcost2=totalcost2+weight;
node[value1].push_back(make_pair(value2,weight));
node[value2].push_back(make_pair(value1,weight));
}
//cout<<totalcost2<<endl;
prim();
int totalCost=0;
for(i=M-1;i>0;i--)
{
//cout<<dist[i]<<"\n";
totalCost+=dist[i];
}
//cout<<totalCost<<endl;
cout<<totalcost2-totalCost<<endl;
}
return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11631 - Dark roads TLE

Your code is now getting wrong answer.
Try input:

Code: Select all

``````3 2
0 1 2000000
1 2 1
0 0
``````
Output should be 0
Check input and AC output for thousands of problems on uDebug!

Karkat_Vantas
New poster
Posts: 4
Joined: Thu Aug 21, 2014 2:59 am

### Re: 11631 - Dark roads

My code returns a compiler error. In my IDE though, it shows no errors, and no warnings except "Unchecked cast from Bag[] to Bag<Main.Edge>[]". The code runs fine on my machine. What are some reasons why the judge would find a different compiling error?

My code also contains different classes (I'm guessing that this is the reason for the error.)
Is

Code: Select all

``````public class Main{
public static void main(String[] args)
{}
public static class A
{}
public static class B
{}
}
``````
the way to arrange multiple classes in the same file?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11631 - Dark roads

Check My Submissions for your CE.
Check input and AC output for thousands of problems on uDebug!

dreamd_hacker
New poster
Posts: 1
Joined: Mon Jun 08, 2015 11:12 am

### Re: 11631 - Dark roads

Hi, I got TLE three times. Here is my code.

Code: Select all

``````#include <cstdio>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#define DEBUG 0
using namespace std;

struct edge {
int f, t, w;
bool operator <(const edge &other) const {
return this-> w < other.w;
}
};

int find_set(int *s, int v){
if(s[v] == v)
return v;
else
return find_set(s, s[v]);
}

int main() {
if (DEBUG)
freopen("in.txt", "r", stdin);

int n, m, f, t, w, par1, par2, total, min_sum, select;
int arr_set;
while (1) {
scanf("%d%d", &n, &m);
if (n == 0 && m == 0)
break;

total = 0;
vector<edge> q;
for(int i = 0; i < m; ++i){
scanf("%d%d%d", &f, &t, &w);
edge e = {f, t, w};
q.push_back(e);
total += w;
arr_set[i] = i;
}
arr_set[n] = n;

if(n == m + 1){
printf("0\n");
continue;
}

min_sum = 0;
select = n - 1;
sort(q.begin(), q.end());
for(int i = 0; (i < m) && select; ++i){
edge t = q[i];
par1 = find_set(arr_set, t.f);
par2 = find_set(arr_set, t.t);
if(par1 != par2){
min_sum += t.w;
arr_set[par1] = par2;
select--;
}
}

printf("%d\n", total - min_sum);
}

return 0;
}

``````

martijnn2008
New poster
Posts: 2
Joined: Sun Aug 31, 2014 5:46 pm

### Re: 11631 - Dark roads

I get a Run Error, can't find out why. Please help.

Code: Select all

``````import java.util.*;

class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
while(n != 0 && m != 0) {
solve(n, m, sc);
n = sc.nextInt();
m = sc.nextInt();
}
}

static class Edge implements Comparable<Edge> {
int a, b, w;
public Edge(int a, int b, int w) {
this.a = a;
this.b = b;
this.w = w;
}

public int compareTo(Edge e) {
return this.w - e.w;
}

public String toString() {
return "[(" + a + ", " + b + ") : " + w + "]";
}
}

static void solve(int n, int m, Scanner sc) {
Edge[] edges = new Edge[m];
Edge[] tree = new Edge[n - 1];
int total = 0;
for (int i = 0; i < m; i++) {
edges[i] = new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt());
total += edges[i].w;
}
parent = new int[n];
rank = new int[n];
int s = 0;
Arrays.sort(edges);
for (int i = 0; i < n; i++) { parent[i] = i; }
for (Edge e : edges) { if (join(e.a, e.b)) { tree[s++] = e; }
if (s >= n -1) break;}
int output = 0;
for (Edge e : tree) {
output += e.w;
}
System.out.println(total - output);
}

static int[] parent;
static int[] rank;
static boolean join(int x, int y) {
/*
int fx = find(x);
int fy = find(y);
if(rank[x] < rank[y])
parent[x] = fy;
else {
parent[y] = fx;
if (rank[x] != rank[y]) {
rank[x]++;
}
}
return fx != fy;
*/

int xrt = find(x);
int yrt = find(y);
if (rank[xrt] > rank[yrt]) {
parent[yrt] = xrt;
} else {
parent[xrt] = yrt;
if (xrt != yrt) {
rank[xrt]++;
}
}
return xrt != yrt;
}

static int find(int x) {
return parent[x] == x ? x : (parent[x] = find(parent[x]));
}

}``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11631 - Dark roads

use class Main
Check input and AC output for thousands of problems on uDebug!