题目大意
给定 n 条线段，每条线段有两个端点坐标。移动时分为两种速度：移动到某条线段的起点/终点使用速度 s，沿着线段绘制使用速度 t。需要选择绘制线段的顺序及每条线段从哪一端开始，求完成全部绘制的最短总时间。
Pass 10/74 WA https://atcoder.jp/contests/abc374/submissions/58484468 赛时代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <iostream>
#include <bitset>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <deque>
using namespace std;
int n,s,t,pos[10][6];
bool vis[10][6],vis2[10];
double ans=10000000,dis;
void dfs(int x,int y,int cnt){
if(cnt>=n){
ans=min(dis,ans);
return;
}
for(int i=1;i<=n;i++){
if(vis2[i]) continue;
vis2[i]=true;
double squareS1=(pos[i][3]-pos[i][1])*(pos[i][3]-pos[i][1]);
double squareS2=(pos[i][4]-pos[i][2])*(pos[i][4]-pos[i][2]);
double lenSeg=sqrt(squareS1+squareS2)/t;
for(int j=1;j<=3;j+=2){
double square1=(pos[i][j]-pos[x][y])*(pos[i][j]-pos[x][y]);
double square2=(pos[i][j+1]-pos[x][y+1])*(pos[i][j+1]-pos[x][y+1]);
double ldis=sqrt(square1+square2)/s;
dis=dis+(ldis+lenSeg);
dfs(i,j,cnt+1);
dis=dis-(ldis+lenSeg);
}
vis2[i]=false;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>s>>t;
for(int i=1;i<=n;i++){
cin>>pos[i][1]>>pos[i][2]>>pos[i][3]>>pos[i][4];
}
dis=0;
dfs(0,0,0);
cout<<ans<<endl;
}
|
只改了一个地方就AC了
dfs(i,4-j,cnt+1); // 进入点和终止点不是一个，这条线段的终止点就是下一条线段的起始点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include <iostream>
#include <bitset>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <deque>
using namespace std;
int n,s,t,pos[10][6];
bool vis[10][6],vis2[10];
double ans=10000000,dis;
void dfs(int x,int y,int cnt){
if(cnt>=n){
ans=min(dis,ans);
return;
}
for(int i=1;i<=n;i++){
if(vis2[i]) continue;
vis2[i]=true;
double squareS1=(pos[i][3]-pos[i][1])*(pos[i][3]-pos[i][1]);
double squareS2=(pos[i][4]-pos[i][2])*(pos[i][4]-pos[i][2]);
double lenSeg=sqrt(squareS1+squareS2)/t;
for(int j=1;j<=3;j+=2){
double square1=(pos[i][j]-pos[x][y])*(pos[i][j]-pos[x][y]);
double square2=(pos[i][j+1]-pos[x][y+1])*(pos[i][j+1]-pos[x][y+1]);
double ldis=sqrt(square1+square2)/s;
dis=dis+(ldis+lenSeg);
dfs(i,4-j,cnt+1);
dis=dis-(ldis+lenSeg);
}
vis2[i]=false;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>s>>t;
for(int i=1;i<=n;i++){
cin>>pos[i][1]>>pos[i][2]>>pos[i][3]>>pos[i][4];
}
dis=0;
dfs(0,0,0);
cout.precision(17);
cout<<ans<<endl;
}
|