10917 - Walk Through the Forest
Moderator: Board moderators
10917 - Walk Through the Forest
I have collected Input for this problem from website.
But I can not check it.Because I have used long type array[1000][1000].
Which is not suported by my visual c++ compiler.
Please give me a good advise.
I am waiting.
But I can not check it.Because I have used long type array[1000][1000].
Which is not suported by my visual c++ compiler.
Please give me a good advise.
I am waiting.
Mr. Arithmetic logic Unit
method for representation of graph with adjancey list is well-known and easy fomular:
you can find them in many books, or internet pages.
and I didn't knew that there exist a compiler which doesn't support 1000 * 1000 32-bit-integer marix.
BTW, In this problem, i guess that the most of input graphs are sparse graph, so I recommend you to use adjency lists/array rather than matrix.
you can find them in many books, or internet pages.
Sure, memory is enough.TISARKER wrote:My another question is : "Can I use long array[1000][1000] in uva judge?"
and I didn't knew that there exist a compiler which doesn't support 1000 * 1000 32-bit-integer marix.
![:oops:](./images/smilies/icon_redface.gif)
BTW, In this problem, i guess that the most of input graphs are sparse graph, so I recommend you to use adjency lists/array rather than matrix.
Sorry For My Poor English.. ![:)](./images/smilies/icon_smile.gif)
![:)](./images/smilies/icon_smile.gif)
-
- Experienced poster
- Posts: 161
- Joined: Tue Oct 25, 2005 8:38 pm
- Location: buet, dhaka, bangladesh
10917 - A Walk Through the Forest
plz clarify me something, i am getting tle. can this problem be solved using backtracking(dfs) within time-limit? output can be at most 2147483647. simply the program below run for near 3 sec in my computer
which algorithm should be used for this problem with a better runtime? i used backtracking(dfs), i used adjacancy list, i pruned whenever a node is found before with a short distance. and one more question, can there be such any input, where a node is numdered with a value greater than n or less than 1? (n is the total number of nodes)
Code: Select all
void main()
{
int i;
for(i = 0; i < 2147483647; ++i)
;
}
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program
----------------
the world is nothing but a good program, and we are all some instances of the program
You can use Dijkstra to find a subgraph in which Jimmy may walk, then use dynamic programming to count paths in it.
Also, read explanation at this page http://www.algorithmist.com/index.php/UVa_10917
Also, read explanation at this page http://www.algorithmist.com/index.php/UVa_10917
-
- Experienced poster
- Posts: 161
- Joined: Tue Oct 25, 2005 8:38 pm
- Location: buet, dhaka, bangladesh
why am i getting wa? i used dijkstra to find distance to all vertices. then i ran the following DP
n_path(dest) = summation of n_path(v), where v is adjacent to dest and distance[v] == distance[dest] - weight[v,dets], is this correct?i read the explanation of the page above, but i dont understand is there any necessity of topological sort?
n_path(dest) = summation of n_path(v), where v is adjacent to dest and distance[v] == distance[dest] - weight[v,dets], is this correct?
Code: Select all
#include <stdio.h>
#include <string.h>
#include <ctype.h>
struct
{
int adj;
int d;
} list[1009][1009];
int n, n_adj[1009], dist[1009], memory[1009];
bool visited[1009];
int extractMin()
{
int i, min = 2147483646, index = -1;
for(i = 0; i < n; ++i)
if(visited[i] == false && dist[i] != -1 && dist[i] < min)
{
min = dist[i];
index = i;
}
return index;
}
void dijkstra()
{
int i, u, v;
memset(dist, -1, sizeof(dist));
memset(visited, false, sizeof(visited));
dist[0] = 0;
for(;;)
{
u = extractMin();
if(u != -1)
visited[u] = true;
else
break;
for(i = 0; i < n_adj[u]; ++i)
{
v = list[u][i].adj;
if(visited[v] == false && (dist[v] == -1 || dist[v] > dist[u] + list[u][i].d))
dist[v] = dist[u] + list[u][i].d;
}
}
}
int n_path(int u)
{
if(u == 0)
return 1;
if(memory[u] != -1)
return memory[u];
int i, count = 0, v;
for(i = 0; i < n_adj[u]; ++i)
{
v = list[u][i].adj;
if(dist[v] != -1 && dist[v] == dist[u] - list[u][i].d)
count += n_path(v);
}
return memory[u] = count;
}
bool exit(char s[], int &m)
{
int i, count = 0, prev = ' ';
for(i = 0; s[i]; ++i)
{
if(isdigit(s[i]) && !isdigit(prev))
++count;
prev = s[i];
}
if(count == 1)
{
sscanf(s, "%d", &n);
if(n == 0)
return true;
}
else if(count == 2)
{
sscanf(s, "%d%d", &n, &m);
return false;
}
else
n /= 0;
return false;
}
void main()
{
int m, x, y, d;
char s[100];
for(;;)
{
scanf(" %[^\n]", s);
if(exit(s, m))
break;
memset(n_adj, 0, sizeof(n_adj));
while(m--)
{
scanf("%d%d%d", &x, &y, &d);
--x;
--y;
list[x][n_adj[x]].adj = y;
list[x][n_adj[x]++].d = d;
list[y][n_adj[y]].adj = x;
list[y][n_adj[y]++].d = d;
}
dijkstra();
memset(memory, -1, sizeof(memory));
printf("%d\n", n_path(1));
}
}
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program
----------------
the world is nothing but a good program, and we are all some instances of the program
-
- Learning poster
- Posts: 74
- Joined: Sat Jul 15, 2006 6:28 am
- Location: CUET , bangladesh
- Contact:
Why WA...
Why WA please help. Can someone give me more input and output.
Code: Select all
cut after AC
Last edited by shakil on Fri May 11, 2007 7:52 am, edited 1 time in total.
SHAKIL
Try the cases.
Input:
Output:
Hope these help.
Input:
Code: Select all
6 11
1 6 2995
6 3 4827
3 1 32391
1 3 153
3 5 12382
5 4 18716
4 3 19895
3 6 21726
6 1 1869
1 5 25667
5 2 17035
10 8
1 4 16803
4 8 6286
8 1 28531
1 10 10722
10 3 22946
3 8 24230
8 6 30570
6 2 19832
0
Code: Select all
3
2
Ami ekhono shopno dekhi...
HomePage
HomePage
lots of WA
What i've done is:
1. Find shortest path from 2 to all vertex using dijkstra
2. build another di graph with edges (u,v) such that d > d[v] in the original graph. that is length of any path from v to 2 is shorter than length of any path from u to 2;
3. count the number of paths from 1 to 2 in the new graph using BFS.
I'm getting WA with this approach. This code passes the inputs given in this post.Can some1 give me some I/O , suggetions plz.
1. Find shortest path from 2 to all vertex using dijkstra
2. build another di graph with edges (u,v) such that d > d[v] in the original graph. that is length of any path from v to 2 is shorter than length of any path from u to 2;
3. count the number of paths from 1 to 2 in the new graph using BFS.
I'm getting WA with this approach. This code passes the inputs given in this post.Can some1 give me some I/O , suggetions plz.
Code: Select all
#include <stdio.h>
#include <vector>
#include <queue>
#include <functional>
#include <string.h>
using namespace std;
#define MAXN 1005
#define INF 999999999
typedef struct node_
{
int u,cost;
} node_;
bool operator < (node_ a,node_ b){ return a.cost > b.cost; }
bool operator > (node_ a,node_ b){ return a.cost < b.cost; }
bool operator == (node_ a,node_ b){ return a.cost == b.cost; }
int v,E;
vector <node_> adj[MAXN];
vector <int> newAdj[MAXN];
int d[MAXN],path[MAXN];
bool visited[MAXN];
priority_queue <node_> PQ;
void dijkstra(int s)
{
int i;
node_ u,next;
for( i = 1; i <= v; i++ )
{
d[i] = INF;
visited[i] = false;
}
d[s] = 0;
u.u = s,u.cost = 0;
while(!PQ.empty()) PQ.pop();
PQ.push(u);
while(!PQ.empty())
{
u = PQ.top();
PQ.pop();
if( visited[u.u] ) continue;
visited[u.u] = true;
for( i = 0; i < adj[u.u].size(); i++ )
{
next = adj[u.u][i];
if( !visited[next.u] )
{
if( d[next.u] > d[u.u] + next.cost )
{
d[next.u] = d[u.u] + next.cost;
PQ.push(next);
}
}
}
}
}
void rebuildGraph()
{
int i,j;
node_ u;
for( i = 1; i <= v; i++ )
{
newAdj[i].clear();
for( j = 0; j < adj[i].size(); j++ )
{
u = adj[i][j];
if( d[i] > d[u.u] ) newAdj[i].push_back(u.u);
}
}
}
void countPath()
{
int i,u,next;
queue <int> Q;
memset(visited,false,sizeof(visited));
memset(path,0,sizeof(path));
path[1] = 1,visited[1] = true;
Q.push(1);
while(!Q.empty())
{
u = Q.front();
Q.pop();
for( i = 0; i < newAdj[u].size(); i++ )
{
next = newAdj[u][i];
if( !visited[next] )
{
visited[next] = true;
path[next] = path[u];
Q.push(next);
}
else path[next] += path[u];
}
}
}
int main()
{
int i,m,n,w;
node_ push;
while(scanf("%d",&v) == 1 && v)
{
scanf("%d",&E);
for( i = 1; i <= v; i++ ) adj[i].clear();
for( i = 0; i < E; i++ )
{
scanf("%d %d %d",&m,&n,&w);
push.u = n;push.cost = w;
adj[m].push_back(push);push.u = m;
adj[n].push_back(push);
}
dijkstra(2);
rebuildGraph();
countPath();
printf("%d\n",path[2]);
}
return 0;
}
Shihab
CSE,BUET
CSE,BUET
Sclo wrote:
This is my function :
Here ct is the number of paths from u to 2.
dist is the distance from 2 to u.
Have i understood something wrong?
& i think Jan's 1st set of input is wrong because :
I have checked that there is no such input in which there is more than one pair of inputs between any pair of nodes.
I have implemented this & getting WA.Try this:
Let d(u) be the distance between vertice u and 2.
then f(u) = sum of f(v) such that u,v are adjacent and d(v)<d(u)
where f(u) is the number of path from u to 2
This is my function :
Code: Select all
int f(int u)
{
int cnt=0,v;
if(u==2)
return 1;
if(ct[u]>=0)
return ct[u];
for(v=1;v<=n;v++)
if(mat[v][u]<inf && dist[v]<dist[u])
cnt+=f(v);
ct[u]=cnt;
return ct[u];
}
dist is the distance from 2 to u.
Have i understood something wrong?
& i think Jan's 1st set of input is wrong because :
There is at most one path between any pair of intersections.
I have checked that there is no such input in which there is more than one pair of inputs between any pair of nodes.
Oh that was fully because of a small mistake in the implementation of dijkstra. ![:oops:](./images/smilies/icon_redface.gif)
Now got AC
Jan's first set of output should be like this:
Ouput is the same as given by him.
![:oops:](./images/smilies/icon_redface.gif)
Now got AC
![:D](./images/smilies/icon_biggrin.gif)
Jan's first set of output should be like this:
Code: Select all
6 9
1 6 2995
6 3 4827
3 1 32391
3 5 12382
5 4 18716
4 3 19895
6 1 1869
1 5 25667
5 2 17035