Page 3 of 4

Posted: Fri Aug 22, 2003 3:49 am
by standlove
Bellman-Ford is best for this problem,
and the complexity is O(NE)

when you detect an edge on a negative cycle in the Nth relaxation,
it means that all vetices reachable from these two vetex (on this edge)
can be reduce to -infinity, so after the Bellman, run a DFS for every
negative vetex~

also check for the Disgusting nodes with index larger than N :(

Posted: Thu Oct 16, 2003 12:22 pm
by Subeen
I m getting WA with the code below: :)
please help.
[c]#include <stdio.h>

#define MAXEDGE 40210
#define MAXNODE 202
#define INF 1000000000L

struct s
{
int x;
int y;
int w;
}edge[MAXEDGE];

long d[MAXNODE];
int busyness[MAXNODE];
int containsCycle[MAXNODE];

int n, m; /* n -> number of vertices, m -> number of edges */

void bellman_ford(int s)
{
int i, j;
for(i=0; i<=n; i++)
d = INF;
d[s] = 0;

for(i=0; i<n; i++)
for(j=0; j<m; j++)
if(d[edge[j].y] > d[edge[j].x] + edge[j].w)
d[edge[j].y] = d[edge[j].x] + edge[j].w;

for(i=0; i<m; i++)
if(d[edge.y] > d[edge.x] + edge.w)
{
d[edge.y] = d[edge.x] + edge.w;
containsCycle[edge.y] = 1; /* the vertex must have negative cycle*/
}
}

void main()
{
int set=1, i, q, value, v;

while(1==scanf("%d", &n))
{
busyness[0] = 0;
for(i=1; i<=n; i++) scanf("%d", &busyness);

scanf("%d", &m); /*m > edges*/
for(i=0; i<m; i++)
{
scanf("%d%d", &edge.x, &edge[i].y);
value = busyness[edge[i].y] - busyness[edge[i].x];
edge[i].w = value * value * value;
}

for(i=0; i<=n; i++) containsCycle[i] = 0;
bellman_ford(1);

scanf("%d", &q);
printf("Set #%d\n", set++);
while(q--)
{
scanf("%d", &v);
if(containsCycle[v]) /* if the vertex has cycle */
printf("?\n");
else if(d[v]!=INF && d[v]>=3)
printf("%ld\n", d[v]);
else
printf("?\n"); /* if unreachable or < 3 */
}
}
}
[/c]

scanf returning EOF

Posted: Mon Oct 20, 2003 2:21 pm
by shamim
I was solving 10449(Traffic):

this was my breaking condition for, ending the program.

[cpp]while (scanf("%ld",&n)!=EOF )[/cpp]

I was getting TLE and I could not figure out what was going on. I nearly gave up, when someone suggested that I change the above line to
[cpp]while (scanf("%ld",&n)==1 )[/cpp]

to my surprise, I got AC.

I have used similar statements for all the problem I have solved which requires the data to be read until end of file. It worked on all those occasions. But why did it not work for this problem.

I would be happy if someone could give any suggestion.

Posted: Mon Oct 20, 2003 3:18 pm
by Dominik Michniewski
scanf() returns number of correctly scanned fields, so EOF isn't good thing for it (EOF means -1 in many operating systems).

I think that your first while loop executes many times, because of scanf

Best regards
DM

WA

Posted: Sat Dec 11, 2004 6:09 pm
by Moha
what's wrong with this code?
[cpp]
i have removed this
[/cpp]
I think(Think!!) my solutuion is correct but I got WA. can anybody send some I/O.

Accepted

Posted: Sat Dec 11, 2004 7:03 pm
by Moha
after sending my source code i found a bug in my code in relaxing "IF".
i change my code to this
[cpp] if(v[edge[j].t]>v[edge[j].s]+graph[edge[j].s][edge[j].t]&&v[edge[j].s]!=inf)[/cpp]
now i accepted!

10449-----WA!!!

Posted: Wed Jan 25, 2006 3:48 pm
by shihabrc
I've used bellman-ford to solve this prob. I've also checked for neg-weight cycles. But i'm gettin WA. Plz. somebody hlp;

Code: Select all


#include<stdio.h>
#include<math.h>
#define INF 99999999

typedef struct Edge{
	int u,v,w;
} Edge;

Edge edge[20000];
int cost[210];
int v,E;
int d[210];
int n_c[210];

void main(void){
	int i,j,k,m,q,count=0;

	while(scanf("%d",&v)==1){
		
		count++;
		for(i=1;i<=v;i++) scanf("%d",&cost[i]);

		scanf("%d",&E);

		for(i=0;i<E;i++){
			scanf("%d %d",&edge[i].u,&edge[i].v);
			edge[i].w=(int)pow((cost[edge[i].v]-cost[edge[i].u]),3.0);
		}

		for(j=1;j<=v;j++){
			d[j]=INF;
			n_c[j]=0;
		}
		d[1]=0;

		for(j=0;j<v-1;j++){
			for(k=0;k<E;k++){
				if(d[edge[k].v]>d[edge[k].u]+edge[k].w) d[edge[k].v]=d[edge[k].u]+edge[k].w;
			}
		}


		for(j=0;j<v-1;j++){
			for(k=0;k<E;k++){
				if(d[edge[k].v]>d[edge[k].u]+edge[k].w) n_c[edge[k].v]=1;
			}
		}

		scanf("%d",&q);
		
		printf("Set #%d\n",count);

		for(i=0;i<q;i++){
			scanf("%d",&m);
			if(d[m]<3) puts("?");
			else if(n_c[m]==1) puts("?");
			else if(d[m]==INF) puts("?");
			else if(d[m]>=3 && d[m]!=INF) printf("%d\n",d[m]);
		}
	}
}
Plz. somebody hlp.(I/O,Sugg,.. anything).

-Shihab

Getting WA Anyone please tell :( :(

Posted: Sun Nov 18, 2007 4:49 am
by zooom

Code: Select all

Finally Accepted 


For all those trying to solve this

Remember some inputs are greater then node number . so output "?" for them.
For all negative cycles output "?" for that node.
For all unreachable destinations output "?"
For all <3 destns output "?"

Hope That helps all .... :D :D :D

Re:

Posted: Sat Apr 17, 2010 2:01 pm
by mak(cse_DU)
Dominik Michniewski wrote:I still got WA ....
Could anyone tell me what's maybe wrong or give me some additional test cases ? I become right results for sample input and for Adrian tests ...
Regards
Dominik
I just solve it using modified BFS( surely using queue( not priority_queue)).
try this input:

Code: Select all

6 6 7 8 9 10 100
6
1 2
2 3
3 4
1 5
5 4
4 5
3
6
4
5
AC output:

Code: Select all

Set #1
?
3
4

Re: 10449 - Traffic

Posted: Sat Jun 18, 2011 1:55 pm
by zobayer
I was trying to solve this problem for a while, getting wrong answer. Here is my code, please give me some test cases where it fails, or point out the bug..
My approach:
Run bellman ford considering 0 as source
Then from all such nodes which still can be updated, I used dfs to mark all reachable nodes from this node, (as those can be visited via the negative cycle one.
Here is my code

Code: Select all

Removed after being accepted.
[edit]
The above logic was ok, I forgot to check connectivity issue "properly".

Re: 10449 - Traffic

Posted: Thu Sep 19, 2013 3:45 pm
by cosmin79
Could anyone clarify how can a negative cycle exist in this problem? I find the statement quite confusing. Assuming we have a negative cycle with nodes x1 -> x2 -> ... xk -> x1, the sum of all edges on the cycles is val[x2] - val[x1] + val[x3] - val[x2] + ... val[xk] - val[x(k-1)] + val[x1] - val[xk] = 0. Thank you in advance!

Re: 10449 - Traffic

Posted: Thu Sep 19, 2013 9:54 pm
by brianfry713
the city authority gets the amount (busyness of destination – busyness of source)^3 from the traveler.

Input:

Code: Select all

3 10 1 5
3
1 2
2 3
3 1
1
2
AC output:

Code: Select all

Set #1
?

Re: 10449 - Traffic

Posted: Thu Sep 19, 2013 10:38 pm
by cosmin79
It makes so much more sense now (for some reason I didn't pay attention to the ^ 3 and the example test cases weren't revealing). I got accepted changing the cost of the edge accordingly.
@brianfry: Thank you!

10449 - Traffic

Posted: Tue Sep 24, 2013 3:42 pm
by phantom11
I am getting Runtime Error for this problem.
My algo is to run bellman ford to find all vertices in negative weight cycles and then run dfs for all nodes reachable by the ones in the negative weight cycles.
I have also taken care that the vertex should be in the range [0,n-1] and it passes all test cases given in this forum. Still i get RE. Can someone please report why ? I have attached my code for reference.

Code: Select all

import java.io.OutputStreamWriter;
import java.io.BufferedWriter;
import java.util.PriorityQueue;
import java.io.BufferedReader;
import java.util.Comparator;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.AbstractCollection;
import java.io.Writer;
import java.util.LinkedList;
import java.util.Collection;
import java.util.List;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.Queue;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Lokesh Khandelwal
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		Traffic_10449 solver = new Traffic_10449();
		solver.solve(1, in, out);
		out.close();
	}
}

class Traffic_10449 {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        String s;
        int n, i, m, u, v, q, test = 0;
        int limit = (1<<27);
        s = in.nextString();
        while (s != null) {
            test++;
            StringTokenizer a = new StringTokenizer(s);
            n = Integer.parseInt(a.nextToken());
            List<Edge> graph[] = new List[n];
            Vertex vertex[] = new Vertex[n];
            int busyness[] = new int[n];
            for(i=0;i<n;i++) {
                vertex[i] = new Vertex(i, limit);
                graph[i] = new ArrayList<Edge>();
                busyness[i] = Integer.parseInt(a.nextToken());
            }
            m = in.nextInt();
            for(i=0;i<m;i++) {
                u = in.nextInt() - 1;
                v = in.nextInt() - 1;
                if(u >= 0 && v >= 0 && u < n && v < n)
                graph[u].add(new Edge(vertex[v], (int)Math.pow(busyness[v] - busyness[u], 3)));
            }
            GraphUtils.bellmanFord(graph, vertex, 0, n);
            boolean isOnNegativeCycle[] = new boolean[n];
            for(i=0;i<n;i++) {
                for(Edge e : graph[i]) {
                    if(vertex[i].key + e.cost < e.dest.key) {
                        isOnNegativeCycle[i] = true;
                        isOnNegativeCycle[e.dest.index] = true;
                    }
                }
            }
            boolean visited[] = new boolean[n];
            for(i=0;i<n;i++) {
                if(!visited[i] && isOnNegativeCycle[i]) {
                    dfs(i, graph, visited);
                }
            }
            for(i=0;i<n;i++) {
                if(visited[i])
                    isOnNegativeCycle[i] = true;
            }
            q = in.nextInt();
            out.printLine("Set #"+test);
            for(i=0;i<q;i++) {
                u = in.nextInt() - 1;
                if(u < 0 || u >= n || vertex[u].key == limit || isOnNegativeCycle[u] || vertex[u].key < 3) {
                    out.printLine("?");
                }
                else out.printLine(vertex[u].key);
            }
            s = in.nextString();
        }
    }
    public void dfs(int index, List<Edge> graph[], boolean visited[]) {
        visited[index] = true;
        for(Edge e : graph[index]) {
            if(!visited[e.dest.index]) {
                dfs(e.dest.index, graph, visited);
            }
        }
    }
}

class InputReader
{
    BufferedReader in;
    StringTokenizer tokenizer=null;

    public InputReader(InputStream inputStream)
    {
        in=new BufferedReader(new InputStreamReader(inputStream));
    }
    public String next()
    {
        try{
            while (tokenizer==null||!tokenizer.hasMoreTokens())
            {
                tokenizer=new StringTokenizer(in.readLine());
            }
            return tokenizer.nextToken();
        }
        catch (IOException e)
        {
            return null;
        }
    }
    public int nextInt()
    {
        return Integer.parseInt(next());
    }
    public String nextString()
    {
        try {
            return in.readLine();
        }
        catch (Exception e)
        {
            return null;
        }

    }
}

class OutputWriter {
	private final PrintWriter writer;

	public OutputWriter(OutputStream outputStream) {
		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
	}

	public OutputWriter(Writer writer) {
		this.writer = new PrintWriter(writer);
	}

	public void print(Object...objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}

	public void printLine(Object...objects) {
		print(objects);
		writer.println();
	}

	public void close() {
		writer.close();
	}
}

class Edge {
    public Vertex dest;
    public int cost;
    public Edge(Vertex dest, int cost) {
        this.dest = dest;
        this.cost = cost;
    }
}

class Vertex implements Comparable<Vertex> {
    public boolean visited;
    public int parent, key, index, indexInHeap;
    public List<Edge> edges;
    public Vertex(int index) {
        this.index = index;
        visited = false;
        parent = -1;
        key = Integer.MAX_VALUE;
        edges = new ArrayList<Edge>();
        indexInHeap = index;
    }
    public Vertex(int index, int key) {
        this.index = index;
        visited = false;
        parent = -1;
        this.key = key;
        edges = new ArrayList<Edge>();
        indexInHeap = index;
    }
    public int compareTo(Vertex o) {
        return this.key - o.key;
    }
}

class GraphUtils {

    public static void bellmanFord(List<Edge> graph[], Vertex a[], int source, int vertexCount) {
        int i, j;
        a[source].key = 0;
        for(i=0;i<vertexCount-1;i++) {  // run loop n-1 times
            for(j=0;j<vertexCount;j++) {
                for(Edge e : graph[j]) {  // relax all edges
                    if(a[j].key + e.cost < e.dest.key) {
                        e.dest.key = a[j].key + e.cost;
                        e.dest.parent = a[j].index;
                    }
                }
            }
        }
        /*check for negative cycle
        for(i=0;i<vertexCount;i++) {
            for(Edge e : graph[i]) {
                if(a[i].key + e.cost < e.dest.key)
                    return true;
            }
        }
         */
    }
    }


Re: 10449 - Traffic

Posted: Fri Oct 11, 2013 2:08 am
by brianfry713
try n = 0