QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#167276 | #7184. Transport Pluses | ucup-team266# | WA | 241ms | 4312kb | C++14 | 2.5kb | 2023-09-07 13:22:02 | 2023-09-07 13:22:02 |
Judging History
answer
/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest
9. module on time
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int INF=1e18;
int n,t;
int sx,sy,tx,ty;
int X[105],Y[105];
int okx[105],oky[105];
int dist[105][105],vis[105][105];
array<int,3> prv[105][105];
void solve()
{
cin>>n>>t;
cin>>sx>>sy>>tx>>ty;
for(int i=1;i<=n;i++) cin>>X[i]>>Y[i];
memset(dist,0x3f,sizeof(dist));
memset(prv,-1,sizeof(prv));
dist[sx][sy]=0;
int tot=0;
while(1)
{
int x=-1,y=-1;
for(int i=0;i<=100;i++) for(int j=0;j<=100;j++) if(!vis[i][j])
{
if(x==-1) x=i,y=j;
else if(dist[i][j]<dist[x][y]) x=i,y=j;
}
if(x==-1) break;
tot++;
// cout<<x<<" "<<y<<" "<<tot<<"\n";
vis[x][y]=1;
memset(okx,0,sizeof(okx));
memset(oky,0,sizeof(oky));
for(int i=1;i<=n;i++) if(X[i]==x||Y[i]==y) okx[X[i]]=oky[Y[i]]=1;
for(int i=0;i<=100;i++) for(int j=0;j<=100;j++)
{
if(i==x&&dist[x][y]+abs(j-y)<dist[i][j]) dist[i][j]= dist[x][y]+abs(j-y),prv[i][j]={0,x,y};
if(j==y&&dist[x][y]+abs(i-x)<dist[i][j]) dist[i][j]=dist[x][y]+abs(i-x),prv[i][j]={0,x,y};
if((okx[i]||oky[j])&&dist[x][y]+t<dist[i][j]) dist[i][j]=dist[x][y]+t,prv[i][j]={1,x,y};
}
}
double ans=1e9;
int x=-1,y=-1;
for(int i=0;i<=100;i++) for(int j=0;j<=100;j++)
{
int d=(i-tx)*(i-tx)+(j-ty)*(j-ty);
double nw=(double)(dist[i][j])+(double)(sqrt((double)(d)));
if(nw<ans) ans=nw,x=i,y=j;
}
vector <array<int,3> > ansv;
cout<<fixed<<setprecision(12)<<ans<<"\n";
if(x!=tx||y!=ty) ansv.pb({0,tx,ty});
while(1)
{
int op=prv[x][y][0],x2=prv[x][y][1],y2=prv[x][y][2];
if(op==-1) break;
ansv.pb({op,x,y});
x=x2,y=y2;
}
cout<<ansv.size()<<"\n";
for(int i=(int)(ansv.size())-1;i>=0;i--) cout<<ansv[i][0]<<" "<<ansv[i][1]<<" "<<ansv[i][2]<<"\n";
}
signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 241ms
memory: 4312kb
input:
1 2 1 1 5 3 6 2
output:
4.000000000000 3 0 1 2 1 5 2 0 5 3
result:
ok correct
Test #2:
score: -100
Wrong Answer
time: 240ms
memory: 4176kb
input:
2 1 1 1 6 1 1 3 6 3
output:
2.000000000000 2 1 0 3 1 6 1
result:
wrong answer step 2: target (6.000000, 1.000000) not on plus (1.000000, 3.000000)