10449 - Traffic
Moderator: Board moderators
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
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
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]
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
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.
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.
-
- 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
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)
Born from ashes - restarting counter of problems (800+ solved problems)
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!
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!!!
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;
Plz. somebody hlp.(I/O,Sugg,.. anything).
-Shihab
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]);
}
}
}
-Shihab
Shihab
CSE,BUET
CSE,BUET
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 ....
-
- Learning poster
- Posts: 72
- Joined: Tue May 30, 2006 5:57 pm
- Location: bangladesh
Re:
I just solve it using modified BFS( surely using queue( not priority_queue)).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
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
Code: Select all
Set #1
?
3
4
Mak
Help me PLZ!!
Help me PLZ!!
-
- Experienced poster
- Posts: 110
- Joined: Tue May 06, 2008 2:18 pm
- Location: CSE-DU, Bangladesh
- 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
[edit]
The above logic was ok, I forgot to check connectivity issue "properly".
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.
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!
-
- 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:AC output:
Input:
Code: Select all
3 10 1 5
3
1 2
2 3
3 1
1
2
Code: Select all
Set #1
?
Check input and AC output for thousands of problems on uDebug!
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!
@brianfry: Thank you!
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.
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;
}
}
*/
}
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA