3181915_wa.cc

北大大牛代码 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];
queue <node> que;

double dist(int a,int b)
{
	return hypot(pt[a].x-pt[b].x,pt[a].y-pt[b].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);
	for(i = 0; i < m; i++)
	{
		a = bak[i].a;
		b = bak[i].b;
		t = bak[i].t;
		double disa = dist(a,0);
		double disb = dist(b,0);
		if(disa == disb)
			continue;
		node pp;
		pp.t = t;
		if(disa < disb)
		{
			pp.u = b;
			map[a].push_back(pp);
		}
		else
		{
			pp.u = a;
			map[b].push_back(pp);
		}
	}
	n = n+2;
	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,0);
			double dis2 = dist(tmp.u,0);
			double tm = dis1 / v;

			if(tt.u==n-1||(dis1 > dis2 && 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;
}