11693 - Speedy Escape

All about problems in Volume 116. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Mohamed Abd El-Monem
New poster
Posts: 15
Joined: Mon Mar 31, 2008 1:20 am
Location: Egypt
Contact:

11693 - Speedy Escape

Post by 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
New poster
Posts: 15
Joined: Mon Mar 31, 2008 1:20 am
Location: Egypt
Contact:

Re: 11693 - Speedy Escape

Post by Mohamed Abd El-Monem »

hey :D

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 11693 - Speedy Escape

Post by 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
Heal The World

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 11693 - Speedy Escape

Post by 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?? :o :o :o
Heal The World

MSH
New poster
Posts: 5
Joined: Sat Aug 23, 2008 8:25 am
Location: Iran
Contact:

Re: 11693 - Speedy Escape

Post by MSH »

calicratis19 wrote: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?? :o :o :o
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.
Mohammad Shokri

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 11693 - Speedy Escape

Post by calicratis19 »

thanks MSH for your reply. i understand the mistake.i am going to fix my code. :)
Heal The World

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 11693 - Speedy Escape

Post by calicratis19 »

Got wa again :o :o
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  ;
}
Heal The World

buiutripa
New poster
Posts: 6
Joined: Wed Oct 21, 2009 1:44 am

Re: 11693 - Speedy Escape

Post by 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/

Post Reply

Return to “Volume 116 (11600-11699)”