3182151_ac_2087ms_8600k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>
#include <queue>
#include <vector>
#define MAXN 50010
#define inf 2100000000

using namespace std;

struct point
{
	double x, y;
};

struct node
{
	int u;
	double t;
};

vector <node> map[MAXN];
point pt[MAXN];
double dis[MAXN], dist[MAXN];
queue <node> que;

double Distance(int a)
{
	return hypot(pt[a].x-pt[0].x,pt[a].y-pt[0].y);
}

struct NODE
{
	int a, b;
	double t;
}bak[200001];

int main()
{
	int n, m;
	double v, t;
	int a, b;
	int i;

	scanf("%d%d%lf",&n,&m,&v);
	for(i = 1; i <= n; i++)
	{
		scanf("%lf%lf",&pt[i].x,&pt[i].y);
	}
	for(i = 0; i < m; i++)
	{
		scanf("%d%d%lf",&bak[i].a,&bak[i].b,&bak[i].t);
	}
	scanf("%lf%lf%lf%lf",&pt[0].x,&pt[0].y,&pt[n+1].x,&pt[n+1].y);
	n = n + 2;
	for(i = 0; i < n; i++)
	{
		dist[i] = Distance(i);
	}
	for(i = 0; i < m; i++)
	{
		a = bak[i].a;
		b = bak[i].b;
		t = bak[i].t;
		node pp;
		pp.t = t;
		if(a==b)
			continue;
		double disa = dist[a];
		double disb = dist[b];
		if(disa == disb)
		{
			if(a!=n+1&&b!=n+1)
				continue;
			else
			{
				if(b==n-1)
				{
					pp.u = b;
					map[a].push_back(pp);
				}
				else
				{
					pp.u = a;
					map[b].push_back(pp);
				}
			}
		}
		if(disa < disb||b==n-1)
		{
			pp.u = b;
			map[a].push_back(pp);
		}
		if(disa > disb||a==n-1)
		{
			pp.u = a;
			map[b].push_back(pp);
		}
	}
	for(i = 0; i < n; i++)
	{
		dis[i] = inf;
	}
	dis[0] = 0;
	node tmp;
	tmp.t = 0;
	tmp.u = 0;
	que.push(tmp);
	while(!que.empty())
	{
		tmp = que.front();
		que.pop();
		for(i = 0; i < map[tmp.u].size(); i++)
		{
			node tt = map[tmp.u][i];
			double dis1 = dist[tt.u];
			double tm = dis1 / v;

			if(tt.u==n-1|| tm > tmp.t+tt.t )
			{
				if(dis[tt.u] > tmp.t+tt.t)
				{
					dis[tt.u] = tmp.t+tt.t;
					node pp;
					pp.t = dis[tt.u];
					pp.u = tt.u;
					que.push(pp);
				}
			}
			
		}
	}
	if(dis[n-1]==inf)
		puts("Impossible");
	else
		printf("%.0lf\n",dis[n-1]);
	return 0;
}