1112 - Mice and Maze

[tzupengwang]

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[105];

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;
}

[brianfry713]

I used Floyd Warshall.

[tzupengwang]

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!!!

[draconian devil]

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()
{	
	//freopen("read.txt","r",stdin);
	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();
	}
}

[brianfry713]

It looks like you figured it out.

[Mukit Chowdhury]

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... :/

[brianfry713]

Change line 52 to:
bool operator < (const dij& p) const {return w>p.w;}

[Mukit Chowdhury]

Thanks a lot ..
Understood the reason...
My bad.... :/

[Repon kumar Roy]

Thanks Brainfry

Code: Select all

Cut after AC

For Flyod Warshal MEMSET_INF 0x3F
it really worked for me

[brianfry713]

Your code overflows, one way to fix it would be change MEMSET_INF to 0x3F

[brianfry713]

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.

[Ripon Azad_uiu]

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[110][110];
int d[110];
int pi[110];
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;
}

[unlucky]

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[2000];
bool visited[2000];

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[200];
        vector<long long int> cost [200];
       // 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;
}

[anando_du]

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