## 10449 - Traffic

Moderator: Board moderators

standlove
New poster
Posts: 4
Joined: Sat Oct 19, 2002 12:33 pm
Location: ZJTU of CHINA
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 StandLove

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:
I m getting WA with the code below: [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;
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]

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

### scanf returning EOF

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.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

### WA

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.
Last edited by Moha on Mon Dec 13, 2004 1:03 am, edited 1 time in total.

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

### Accepted

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!

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

### 10449-----WA!!!

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;
int cost;
int v,E;
int d;
int n_c;

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=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
Shihab
CSE,BUET

zooom
New poster
Posts: 4
Joined: Tue Jun 12, 2007 9:20 am

### Getting WA Anyone please tell :( :(

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 ....   mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm

### Re:

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``````
Mak
Help me PLZ!!

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Contact:

### Re: 10449 - Traffic

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.
``````

The above logic was ok, I forgot to check connectivity issue "properly".
You should not always say what you know, but you should always know what you say.

cosmin79
New poster
Posts: 11
Joined: Fri Aug 09, 2013 7:25 pm

### Re: 10449 - Traffic

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!

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

### Re: 10449 - Traffic

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
?
``````
Check input and AC output for thousands of problems on uDebug!

cosmin79
New poster
Posts: 11
Joined: Fri Aug 09, 2013 7:25 pm

### Re: 10449 - Traffic

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!

phantom11
New poster
Posts: 7
Joined: Thu Sep 12, 2013 12:36 am

### 10449 - Traffic

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.util.Comparator;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.AbstractCollection;
import java.io.Writer;
import java.util.Collection;
import java.util.List;
import java.io.IOException;
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;
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);
}
}
}
}

{
StringTokenizer tokenizer=null;

{
}
public String next()
{
try{
while (tokenizer==null||!tokenizer.hasMoreTokens())
{
}
}
catch (IOException e)
{
return null;
}
}
public int nextInt()
{
return Integer.parseInt(next());
}
public String nextString()
{
try {
}
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;
}
}
*/
}
}

``````

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

### Re: 10449 - Traffic

try n = 0
Check input and AC output for thousands of problems on uDebug!