OJ Board

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

Code: Select all

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

Code: Select all

5333.3333333333

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

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

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