11693 - Speedy Escape

[Mohamed Abd El-Monem]

Hi all,

I got WA in this problem this is what I do:-
1- calculate the shortest path between the brothers start and all exits using dijkstra.
1- calculate the shortest path between the police start and all exits using dijkstra.
3- for(i = 0 to e)
if (brotherDistance > policeDistance)
continue;
else
calc time the police will take then calc the speed with that time and take the min speed of all speeds.

4- if there is no speed print IMPOSSIBLE.
else
print the speed.


this is my code:

Code: Select all

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stdio.h>
#include <queue>
using namespace std;


class Graph
{
public:
	vector< vector< pair<int, int> > > AdjList;
	int NumOfVertices;
	Graph(int NOV)
	{
		NumOfVertices = NOV;
		AdjList.resize(NumOfVertices);
	}
	bool InsertEdge(int x, int y, int weight, bool Directed)
	{
		if ( x > NumOfVertices || y > NumOfVertices )
			return false;

		AdjList[x].push_back(make_pair(weight, y));
		if(!Directed)
			InsertEdge(y, x, weight, true);
		return true;
	}
};



class Dijkstra
{
public:
	vector<int> Distance;

	Dijkstra(int NOV)
	{
		Distance.resize(NOV, 987654321);
	}

	void Go(Graph &G, int Source)
	{
		priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > Q;
		Distance[Source] = 0;
		Q.push(make_pair(0, Source));
		while(!Q.empty())
		{
			pair<int, int> Top = Q.top();
			Q.pop();
			int V = Top.second;
			int D = Top.first;
			if(D <= Distance[V])
			{
				int sz = G.AdjList[V].size();
				for(int i = 0 ; i < sz ; i++)
				{
					int V2 = G.AdjList[V][i].second;
					int D2 = G.AdjList[V][i].first;
					if(Distance[V2] > Distance[V] + D2)
					{
						Distance[V2] = Distance[V] + D2;
						Q.push(make_pair(Distance[V2], V2));
					}
				}
			}
		}
	}
};


int main()
{
	
	int Cases;
	int n, m, e, a, b, w, bs, ps;
	scanf("%d", &Cases);
	while(Cases--)
	{
		scanf("%d %d %d", &n, &m, &e);
		Graph G(n);
		for(int i = 0 ; i < m ; i++)
		{
			scanf("%d %d %d", &a, &b, &w);
			G.InsertEdge(a-1, b-1, w, false);
		}
		vector<int> exits(e);
		for(int i = 0 ; i < e ; i++)
			scanf("%d", &exits[i]);

		scanf("%d %d", &bs, &ps);
		int bdist;
		int pdist;
		Dijkstra D1(n), D2(n);
		D1.Go(G, bs - 1);
		D2.Go(G, ps - 1);
		bool flag = false;
		double Speed = INT_MAX;
		for(int i = 0 ; i < e ; i++)
		{
			bdist = D1.Distance[exits[i]-1];
			pdist = D2.Distance[exits[i]-1];
			if(bdist > pdist)
			{
				continue;
			}
			else
			{
				double T = double(pdist) / 160;
				double S = double(bdist) / T;
				Speed = min(S, Speed);
				flag = true;
			}
		}

		if(flag)
			cout << fixed << setprecision(7) << Speed << endl;
		else
			printf("IMPOSSIBLE\n");
			

	}
	return 0;
}

any help please.
thanks in advance.

[Mohamed Abd El-Monem]

hey

[calicratis19]

i think your procedure is wrong.
in problem statement it is told that the brothers car is faster than the police. so i think distance doesnt matter.

try this case
input

Code: Select all

1
3 2 1
1 2 100
3 2 3
2
1 3

output

Code: Select all

5333.3333333333

[calicratis19]

getting WA in this prob. i used dijkstra.
my procedure is

1)for all 'e' calculate the distance between police and highway exit and also between brothers and highway exit. while calculating the distance between brothers and highway exit i didn't use the node where the police starts.

2) if the the brothers can reach exits without the node where police were initially ,i store the speed.

3)last i find the min speed and output it.

4)but if there is no speed stored i output impossible.

is this the correct way??

[MSH]

getting WA in this prob. i used dijkstra.
my procedure is

1)for all 'e' calculate the distance between police and highway exit and also between brothers and highway exit. while calculating the distance between brothers and highway exit i didn't use the node where the police starts.

2) if the the brothers can reach exits without the node where police were initially ,i store the speed.

3)last i find the min speed and output it.

4)but if there is no speed stored i output impossible.

is this the correct way??

I think you should also consider times when police arrives to any intersection, that means when you find a path for brothers to a highway, any node on this path should be safe and for this reason, you have to calculate minimum times needed for police to arrive any intersection and then apply your algorithm.

[calicratis19]

thanks MSH for your reply. i understand the mistake.i am going to fix my code.

[calicratis19]

Got wa again
This time i did as msh mentioned . Here is my code.

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define lim 105
#define INF 9999999
int node,edge,high,i,j,bro,pol,k,test,u,v,len,mx,cur,now;
int mat[lim][lim],fn[lim],distance[lim],dis[lim],adj[lim][lim],distn[lim];
double speed,ans,time;
bool flag[lim];

void dijkstra(int st)    //for police
{
        dis[st]=0;
        while(1)
        {
                cur = st;
                flag[cur]=true;
                for( int i=1 ; i<=adj[cur][0] ; i++ )
                {
                        now = adj[cur][i];
                        if(mat[cur][now]+dis[cur] < dis[now] && !flag[now])
                                dis[now] = mat[cur][now] + dis[cur];
                }
                mx = INF;
                for(i=1;i<=node;i++)
                        if(dis[i]!=INF && !flag[i] && mx > dis[i] )
                        {
                                mx = dis[i];
                                st = i;
                        }
                if(mx == INF)break;
        }
}
void second_dijkstra(int st)   // for brothers
{
        distance[st]=distn[st]=0;
        while(1)
        {
                cur = st;
                flag[cur]=true;
                for( int i=1 ; i<=adj[cur][0] ; i++ )
                {
                        now = adj[cur][i];
                        if(dis[now]+distance[cur] > distance[now] && !flag[now])
                        {
                                distance[now] = dis[now] + distance[cur];
                                distn[now] = mat[cur][now] + distn[cur];
                        }
                }
                mx = -1;
                for(i=1;i<=node;i++)
                        if(distance[i]!=-1 && !flag[i] && mx < distance[i] )
                        {
                                mx = distance[i];
                                st = i;
                        }
                if(mx == -1)break;
        }
}
int main()
{
        //freopen("in.txt","r",stdin);
        scanf("%d",&test);
        while( test-- )
        {
                scanf("%d %d %d",&node,&edge,&high);
                for( i=0 ; i<=node ; i++ )
                {
                        flag[i]=false;
                        dis[i]=distn[i]=INF;
                        for( j=0 ;j<=node ; j++ )
                                mat[i][j]=INF;
                        adj[i][0]=0;
                }

                for ( i=0 ; i<edge ; i++ )
                {
                        scanf("%d %d %d",&u,&v,&len);
                        adj[u][++adj[u][0]] = v;
                        adj[v][++adj[v][0]] = u;
                        mat[u][v]=mat[v][u]=len*100;
                }

                for( i=0 ; i<high ; i++ )
                        scanf( "%d" ,&fn[i]);

                scanf("%d %d",&bro,&pol);
                dijkstra(pol);

                for(i=0;i<=node;i++)
                {
                        flag[i]=0;
                        distance[i]=-1;
                }

                flag[pol]=true;
                second_dijkstra(bro);
                ans = INF;

                for(i=0;i<high;i++)
                {
                        if(dis[fn[i]]!=INF && distance[fn[i]]!=-1)
                        {
                                time = (double)distance[fn[i]]/160;
                                if(fabs(time-0)<.000001)speed = 0;
                                else speed =(double) distn[fn[i]]/time;
                                if(ans-speed  >.000001)ans = speed;
                        }
                }

                if(fabs(ans - INF) <.000001)printf("IMPOSSIBLE\n");
                else printf("%.7lf\n",ans);
        }
        return 0  ;
}

[buiutripa]

what's is wrong with this code?

i tested for this test case:

Code: Select all

5

4 3 1
1 2 10
2 3 30
2 4 40
1
4 3

3 2 1
1 2 100
3 2 3
2
1 3

3 2 1
1 2 7
2 3 8
1
3 2

3 2 1
1 2 7
2 3 8
1
2 3

4 4 2
1 4 1
1 3 4
3 4 10
2 3 30
1 2
3 4

and my output:

Code: Select all

213.3333333
5333.3333333
IMPOSSIBLE
74.6666667
137.1428571

Code: Select all

#include <iostream>
#include <climits>
using namespace std;

#define V 100
#define GRAU 100
#define inf 1e10

struct edge { int v; double w; };

int n, m;
bool naarv[V];
int pai[V], grau[V];
double distlad[V], distpol[V];
edge grafo[V][GRAU];

int e, a, b, lad, pol, t;
double l;
int saida[V];

void dij(int s, double dist[], bool ladrao) {
	for (int v = 0; v < n; v++) {
		dist[v] = inf;
		pai[v] = -1;
		naarv[v] = false;
	}
	
	dist[s] = 0;
	int u = s;
	while (!naarv[u]) {
		naarv[u] = true;
	
		for (int i = 0; i < grau[u]; i++) {
			int v = grafo[u][i].v;
			double w = grafo[u][i].w;
			
			if (ladrao && (v == pol)) continue;
			
			if (dist[v] > dist[u] + w) {
				dist[v] = dist[u] + w;
				pai[v] = u;
			}
		}
		
		double menor_dist = inf;
		u = 0;
		for (int v = 0; v < n; v++) {
			if (!naarv[v] && (dist[v] < menor_dist)) {
				menor_dist = dist[v];
				u = v;
			}
		}
	}
}

void init() {
	for (int i = 0; i < n; i++) {
		grau[i] = 0;
	}
}

void read() {
	cin >> n >> m >> e;
	
	init();
	
	while (m--) {
		cin >> a >> b >> l;
		a--; b--;
		l /= 10.0;
	
		grafo[a][grau[a]].v = b;
		grafo[b][grau[b]].v = a;
		grafo[a][grau[a]++].w = grafo[b][grau[b]++].w = l;		
	}
	
	for (int i = 0; i < e; i++) {
		cin >> saida[i];
		saida[i]--;
	}
	
	cin >> lad >> pol;
	lad--; pol--;
}

void process() {
	dij(pol, distpol, false);
	dij(lad, distlad, true);

	bool pode = false;
	double veloc = inf;

	for (int i = 0; i < e; i++) {
		int u = saida[i];
		
		if (distlad[u] != inf) {
			pode = true;
		}
		
		double max_atual = -inf;
		while (u != -1 && u != lad) {
			double vel_atual = (distlad[u]*160)/distpol[u];
			if (vel_atual > max_atual) {
				max_atual = vel_atual;
			}			
			u = pai[u];
		}
		
		if (max_atual < veloc) {
			veloc = max_atual;
		}
	}
	
	if (pode) {
		printf("%.7lf\n", veloc);
	}
	else {
		printf("IMPOSSIBLE\n");
	}
}

int main() {
	cin >> t;
	while (t--) {
		read();
		process();
	}
	return 0;
}

the output of this code has a precision required for this problem?

thanks, o/