Page 1 of 1

### 1112 - Mice and Maze

Posted: Sat Mar 16, 2013 1:44 pm
I get WA with this problem.
Can anyone tell me the tricky part of this problem or is there any mistake with my code?

I turn all edges to the opposite side and run the Dijkstra Algorithm to know the shortest path from every vertex to the exit.
The following is my code
Thanks~

Code: Select all

``````/*1112*/
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

typedef pair<int,int> ii;
typedef vector<ii> vii;
vector<vii> v;
int num,ex,time,edge;
int ans;
priority_queue<ii> pq;
bool vis;

void SSSP()
{
pq.push(ii(0,ex));
vis[ex]=1;
ans++;
while (!pq.empty())
{
ii front=pq.top();pq.pop();
int A=front.first,B=front.second;
for (int i=0;i<v[B].size();i++)
{
ii next=v[B][i];
int na=next.first,nb=next.second;
if (!vis[nb]&&A+na<=time)
{
pq.push(ii(A+na,nb));
vis[nb]=1;
ans++;
}
}
}
}
int main()
{
bool first=1;
int amm;
scanf("%d",&amm);
while (amm--)
{
scanf("%d%d%d%d",&num,&ex,&time,&edge);
ex--;
v.assign(num,vii());
ans=0;

int a,b,c;
for (int i=0;i<edge;i++)
{
scanf("%d%d%d",&a,&b,&c);
v[b-1].push_back(ii(c,a-1));
}
for (int i=0;i<num;i++)
{
sort(v[i].begin(),v[i].end());
}
memset(vis,false,sizeof vis);
SSSP();
if (first)first=0;
else puts("");
printf("%d\n",ans);
}
return 0;
}
``````

### Re: 1112 - Mice and Maze

Posted: Tue Mar 19, 2013 10:51 pm
I used Floyd Warshall.

### Re: 1112 - Mice and Maze

Posted: Wed Mar 20, 2013 11:23 am
BrianFry~Thanks for your advice!! I got AC with Floyd Warshall
but I'm still wondering what's wrong with my Dijkstra Algorithm since it's a single destination shortest path problem!!!

### Re: 1112 - Mice and Maze

Posted: Thu Aug 08, 2013 2:06 pm
Getting WA on this problem. Used Dijkstra. I computed the cost from Source to all other nodes then I checked if the computed cost is greater than given cost.

so Why wrong answer? I know this can be done by floyd warshall easily but what's the problem with Dijkstra?
Here is my code

Code: Select all

``````#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#define N 20000
#define inf 999999999
#define _ ios_base::sync_with_stdio(0);cin.tie(0);

using namespace std;

class node
{
public:
int c,w;
bool operator () (node n1,node n2)
{
return n1.w < n2.w;
}
};
int main()
{
int testcase;
cin >> testcase;
vector <node> v[N];
while(testcase--)
{
int n,m,S,T;
cin >> n >> S >> T;
cin >> m;
while(m--)
{
int p,c,w;
node temp;
cin >> p >> c >> w;
temp.c = c; temp.w = w;
v[p].push_back(temp);
}

vector <int> cost;
cost.assign(n+1,inf);

priority_queue <node, vector<node>, node > pq;

node src;
src.c = S; src.w = 0; cost[S] = 0;

pq.push(src);
while(!pq.empty())
{
node parent = pq.top();
pq.pop();
int a = v[parent.c].size();
for(int i = 0 ; i < a ; i++)
{
node child = v[parent.c][i];
if(cost[parent.c] + child.w < cost[child.c])
{
cost[child.c] = cost[parent.c] + child.w;
pq.push(child);
}
}
}

int a = cost.size();
for(int i = 1 ; i < a ; i++)
if(cost[i] > T)
n--;

cout << n << endl;

if(testcase) cout << endl;
for(int i = 0 ; i <= n ; i++) v[i].clear();
}
}
``````

### Re: 1112 - Mice and Maze

Posted: Thu Aug 08, 2013 9:26 pm
It looks like you figured it out.

### Re: 1112 - Mice and Maze

Posted: Mon Jul 21, 2014 4:30 pm

Code: Select all

``````// Found reason... :)
``````
I'm astonished that, after finding the exit cell, if I try to return from function, I'm given WA... But if I check until queue is empty, it is AC !!! Would anyone please tell me the exact reason ???
It will really help... Thanks in advance...
*** I tried with some cases to find out the bug.... but as I don't know where is the difference, I am failed... :/

### Re: 1112 - Mice and Maze

Posted: Mon Jul 21, 2014 11:23 pm
Change line 52 to:
bool operator < (const dij& p) const {return w>p.w;}

### Re: 1112 - Mice and Maze

Posted: Tue Jul 22, 2014 9:26 pm
Thanks a lot .. Understood the reason... ### Re: 1112 - Mice and Maze

Posted: Tue Sep 30, 2014 1:49 pm
Thanks Brainfry Code: Select all

``````Cut after AC
``````
For Flyod Warshal MEMSET_INF 0x3F
it really worked for me ### Re: 1112 - Mice and Maze

Posted: Tue Sep 30, 2014 4:04 pm
Your code overflows, one way to fix it would be change MEMSET_INF to 0x3F

### Re: 1112 - Mice and Maze

Posted: Tue Sep 30, 2014 9:13 pm
If you memset an int array to something like 0x7F, then each int will have a value of 0x7F7F7F7F. In the Floyd–Warshall algorithm, if you add two of those values, it will overflow a 32-bit signed int.

### Re: 1112 - Mice and Maze

Posted: Sun May 03, 2015 4:14 pm
Why am I getting WA... I used Dijkstra's algorithm.... I can't find my mistake...
please someone help me.. give me some sample inputs.. here is my code...

Code: Select all

``````#include<cstdio>
#include<set>
#include<utility>
#include<iostream>
using namespace std;
#define Key_Value pair<int,int>
#define PriorityQueue set<Key_Value>
int w;
int d;
int pi;
PriorityQueue Q;

void Relax(int u,int v)
{
if(d[v]>d[u]+w[u][v])
{
Q.erase(Key_Value(d[v],v));
d[v]=d[u]+w[u][v];
Q.insert(Key_Value(d[v],v));
pi[v]=u;
}
}
void Initialize_Single_Source(int NofVertices,int Source)
{
for(int i=1;i<=NofVertices;i++)
{
d[i]=1e8;
pi[i]=-1;
}
d[Source]=0;
}
void Dijsktra_Algorithm(int NofVertices,int NofEdges,int Source)
{
Initialize_Single_Source(NofVertices,Source);
for(int i=1;i<=NofVertices;i++)
{
Q.insert(Key_Value(d[i],i));
}
while(!Q.empty())
{
Key_Value u=*Q.begin();
Q.erase(u);
for(int v=1;v<=NofVertices;v++)
{
if(w[u.second][v]!=0)
{
Relax(u.second,v);
}
}
}
}
int main()
{
int n,NofVertices,NofEdges,u,v,weight,source,time;
scanf("%d",&n);
while(n--)
{
scanf("%d",&NofVertices);
scanf("%d",&source);
scanf("%d",&time);
scanf("%d",&NofEdges);
for(int i=1;i<=NofVertices;i++)
{
for(int j=1;j<=NofVertices;j++)
w[i][j]=0;
}
for(int i=1;i<=NofEdges;i++)
{
scanf("%d%d%d",&u,&v,&weight);
w[u][v]=weight;
}
Dijsktra_Algorithm(NofVertices,NofEdges,source);
int sum=0;
for(int i=1;i<=NofVertices;i++)
{
if(d[i]<=time)
sum++;
}
printf("%d\n",sum);
if(n)
printf("\n");
}

return 0;
}``````

### Re: 1112 - Mice and Maze

Posted: Sun Aug 30, 2015 3:51 am
i am getting WA... can't find the reason... pls help me with my code ... need some test case....

Code: Select all

``````#include<iostream>
#include<bits/stdc++.h>

using namespace std;

long long int dis;
bool visited;

struct node
{
int u;
long long int w;
node(int a, long long int b)
{
u=a;w=b;
}

bool operator > (node const &p)const
{
return w>p.w;
}

};

int Dijkstra(int des,long long int time,vector<int> edge[],vector<long long int> cost[])
{
priority_queue<node,vector<node>,greater<node>> Q;

int ans=0;

memset(dis,63,sizeof(dis));
memset(visited,0,sizeof(visited));

dis[des]=0;

Q.push(node(des,0));

while(!Q.empty())
{
node top = Q.top(); Q.pop();

int u=top.u;

if(visited[u]==1) continue;
// cout<<u<<"   dis: "<<dis[u]<<endl;
if(dis[u]<=time)
ans++;
visited[u]=1;

for(int i=0;i<(int)edge[u].size();i++)
{
int v=edge[u][i];

if(cost[u][i]+dis[u]<dis[v])
{
dis[v]= cost[u][i]+dis[u];
Q.push(node(v,dis[v]));
}
}
}

return ans;

}

int main()
{
int test;
cin>>test;

int n,des,E;
long long int time;
for(int i=1;i<=test;i++)
{
vector<int> edge;
vector<long long int> cost ;
// memset(cost,63,sizeof(cost));
cin>>n>>des>>time>>E;

int u,v;
long long int w;

for(int i=0;i<E;i++)
{
cin>>u>>v>>w;
edge[u].push_back(v);
cost[u].push_back(w);

}

if(i>1)
cout<<"\n";

cout<<Dijkstra(des,time,edge,cost)<<endl;
}

return 0;
}
``````

### Re: 1112 - Mice and Maze

Posted: Thu Dec 03, 2015 3:36 pm
Those who are getting wa are running dijkstra from target to destination but running this from u -> v  but the graph should be v -> u  so please reverse the input graph then run your dijkstra  