竞赛讨论区 > Car的旅行路线 快wa疯了,求求大佬帮忙看看
头像
翔村渡渡鸟
发布于 2021-01-27 19:52
+ 关注

Car的旅行路线 快wa疯了,求求大佬帮忙看看

#include<bits/stdc++.h>

using namespace std;
#define N 109
#define M 2600009 
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof a)
#define PII pair<double,double>
#define PII2 pair<double ,int>
int e[M],ne[M],h[M],idx,cnt;
double w[M];
map<PII,int> mp;
const double eps = 1e-6;
double dist[M];
bool st[M];
double s,t,A,B; //城市个数 ,飞机单位历程价格
//A,B分别表示城市A B的序号 
int s1,e1;
struct node
{
	double x[6],y[6],T;
}city[N];
void add(int x,int y,double z)
{
	e[idx] = y;
	w[idx] = z;
	ne[idx] = h[x];
	h[x] = idx++;
}
void Dijstra(int x)
{
	for(int i=1; i<=M; i++) dist[i] = DBL_MAX; 
	mem(st,false); 
	dist[x] = 0;
	priority_queue<PII2,vector<PII2> ,greater<PII2> > heap;
	heap.push({0,x});
	while(heap.size())
	{
		PII2 tmp = heap.top();
		heap.pop();
        double d= tmp.first;
        int p = tmp.second;
		if(st[p]) continue;
		st[p] = true;
		for(int i=h[p]; i!=-1; i=ne[i])
		{
			int j = e[i];
			if(dist[j] > d+w[i])
			{
				dist[j] = d+w[i];
				heap.push({dist[j],j}); 
			}
		}
	}
}
double Dist(double x1,double y1,double x2,double y2)
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
} 
int main()
{
	
	int n;
	cin>>n;
	while(n--)
 	{
 		mp.clear();
 		//cout<<mp.size()<<" mp"<<endl;
 		mem(h,-1);
 		mem(e,0);
 		mem(ne,0);
 		mem(w,0);
 		idx=0;
 		s1=e1=cnt=0;
 		cin>>s>>t>>A>>B;
 		for(int i=1; i<=s; i++)
 		{
 			for(int j=1; j<=3; j++)
 			{
 				cin>>city[i].x[j]>>city[i].y[j];
 				if(!mp[{city[i].x[j],city[i].y[j]}])
				 mp[{city[i].x[j],city[i].y[j]}] = ++cnt;
				if(i==A&&!s1) s1=cnt;
				if(i==B&&!e1) e1 = cnt;
//			    if(i==A)	cout<<cnt<<" ";
//			    if(i==B) cout<<cnt<<" ";
			//	cout<<cnt<<" ";
			}
			//cout<<endl;
			cin>>city[i].T;
			double x1 = city[i].x[1],y1 =city[i].y[1],x2 =city[i].x[2],y2 = city[i].y[2];
			double x3  =city[i].x[3],y3 = city[i].y[3],x4,y4;
			double  a = Dist(x1,y1 ,x2,y2);
			double  b = Dist(x2,y2, x3,y3);
			double  c = Dist(x3,y3, x1,y1);
			if(a*a+b*b-c*c<eps) { 
			city[i].x[4]=x4 = x1+x3-x2; 
			city[i].y[4] = y4 = y1+y3-y2; 
			if(!mp[{x4,y4}]) mp[{x4,y4}] = ++cnt;
			add(mp[{x1,y1}],mp[{x2,y2}],a*city[i].T);
			add(mp[{x2,y2}],mp[{x1,y1}],a*city[i].T);
			add(mp[{x2,y2}],mp[{x3,y3}],b*city[i].T);
			add(mp[{x3,y3}],mp[{x2,y2}],b*city[i].T);
	        add(mp[{x1,y1}],mp[{x4,y4}],b*city[i].T);
	        add(mp[{x4,y4}],mp[{x1,y1}],b*city[i].T);
	        add(mp[{x4,y4}],mp[{x3,y3}],a*city[i].T);
	        add(mp[{x3,y3}],mp[{x4,y4}],a*city[i].T);
			}
			if(a*a+c*c-b*b<eps) { 
			city[i].x[4]=x4 = x2+x3-x1;
			city[i].y[4] = y4=y2+y3-y1;
			if(!mp[{x4,y4}]) mp[{x4,y4}] = ++cnt;
	    	add(mp[{x1,y1}],mp[{x2,y2}],a*city[i].T);
			add(mp[{x2,y2}],mp[{x1,y1}],a*city[i].T);
			add(mp[{x3,y3}],mp[{x4,y4}],a*city[i].T);
			add(mp[{x4,y4}],mp[{x3,y3}],a*city[i].T);
			add(mp[{x1,y1}],mp[{x3,y3}],c*city[i].T);
			add(mp[{x3,y3}],mp[{x1,y1}],c*city[i].T);
			add(mp[{x2,y2}],mp[{x4,y4}],c*city[i].T);
			add(mp[{x4,y4}],mp[{x2,y2}],c*city[i].T);
			}
			if(b*b+c*c-a*a<eps) { 
				city[i].x[4]=x4= x1+x2-x3; 
				city[i].y[4] =y4=y1+y2-y3;
			if(!mp[{x4,y4}]) mp[{x4,y4}] = ++cnt;
	    	add(mp[{x1,y1}],mp[{x4,y4}],b*city[i].T);
			add(mp[{x4,y4}],mp[{x1,y1}],b*city[i].T);
			add(mp[{x3,y3}],mp[{x2,y2}],b*city[i].T);
			add(mp[{x2,y2}],mp[{x3,y3}],b*city[i].T);
			add(mp[{x1,y1}],mp[{x3,y3}],c*city[i].T);
			add(mp[{x3,y3}],mp[{x1,y1}],c*city[i].T);
			add(mp[{x2,y2}],mp[{x4,y4}],c*city[i].T);
			add(mp[{x4,y4}],mp[{x2,y2}],c*city[i].T);
			}	
    }
    //各个城市之间的机场路线建图 
    for(int i=1; i<=s; i++)
    {
    	for(int j=i+1; j<=s; j++)
    	{
    		for(int k=1 ;k<=4; k++)
    		{
    			for(int l=1; l<=4; l++)
    			{
    				int u = mp[{city[i].x[k],city[i].y[k]}];
    				int v = mp[{city[j].x[l],city[j].y[l]}];
    				double d = t*Dist(city[i].x[k],city[i].y[k],city[j].x[l],city[j].y[l]);
    				//cout<<u<<" "<<v<<" "<<d<<endl; 
    				add(u,v,d);
    				add(v,u,d);
				}
			}
		}
	}
	//cout<<s1<<" "<<e1<<endl;
	double ans = DBL_MAX;
	for(int i=s1; i<=s1+3; i++)
	{
		Dijstra(i);
		for(int j=e1; j<=e1+3; j++)
		{
			//cout<<i<<" "<<j<<endl; 
			ans = min(ans,dist[j]);
		}	
	}
	printf("%.1f\n",ans);
}
	return 0;
 } 

全部评论

(0) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐