题解：
这道题两步： 建图+Dijstra
难点: 建图
- 对于同一个城市的4个飞机场，两两之间都应该建一条路，w=dist*city[i].T, 我最先一直以为只有矩阵的四条边。。。，一直wa
- 不同城市之间的飞机场，两两之间建一条路,w=dist*t
- 求第四个点：这里不多赘述，利用平行四边形性质即可，参考大佬博客洛谷大佬
AC代码
#include<bits/stdc++.h>
using namespace std;
#define N 109
#define M 160000+9
#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-8;
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()
{
for(int i=1; i<=M; i++) dist[i] = DBL_MAX;
mem(st,false);
dist[s1] = 0,dist[s1+1] = 0,dist[s1+2]=0, dist[s1+3]=0;
priority_queue<PII2,vector<PII2> ,greater<PII2> > heap;
heap.push({
0,s1}),heap.push({
0,s1+1}),heap.push({
0,s1+2}),heap.push({
0,s1+3});
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;
}
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(a*a+c*c-b*b<eps) {
city[i].x[4]=x4 = x2+x3-x1;
city[i].y[4] = y4=y2+y3-y1;
}
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;
}
//各个城市之间的机场路线建图
for(int i=1; i<=s; i++)
{
for(int j=i; 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;
if(i==j) d = city[i].T*Dist(city[i].x[k],city[i].y[k],city[j].x[l],city[j].y[l]);
else d = t*Dist(city[i].x[k],city[i].y[k],city[j].x[l],city[j].y[l]);
add(u,v,d);
add(v,u,d);
}
}
}
}
//cout<<s1<<" "<<e1<<endl;
double ans = DBL_MAX;
Dijstra();
for(int i=e1; i<=e1+3; i++)
{
ans = min(ans,dist[i]);
}
printf("%.1f\n",ans);
}
return 0;
}
wa代码
对于同一个城市，我只建立了四条边，即矩阵的四条边
#include<bits/stdc++.h>
using namespace std;
#define N 109
#define M 160000+9
#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-8;
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()
{
for(int i=1; i<=M; i++) dist[i] = DBL_MAX;
mem(st,false);
dist[s1] = 0,dist[s1+1] = 0,dist[s1+2]=0, dist[s1+3]=0;
priority_queue<PII2,vector<PII2> ,greater<PII2> > heap;
heap.push({
0,s1}),heap.push({
0,s1+1}),heap.push({
0,s1+2}),heap.push({
0,s1+3});
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);
mem(city,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;
}
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=1; j<=s; j++)
{
for(int k=1 ;k<=4; k++)
{
for(int l=1; l<=4; l++)
{
if(i==j) continue;
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;
Dijstra();
for(int i=e1; i<=e1+3; i++) ans = min(ans,dist[i]);
printf("%.1f\n",ans);
}
return 0;
}
京公网安备 11010502036488号