QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #165308 | #7184. Transport Pluses | ucup-team1001# | WA | 1ms | 3696kb | C++14 | 4.0kb | 2023-09-05 17:25:42 | 2023-09-05 17:25:43 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn=100+5;
int xx[maxn],yy[maxn],n,t;
double dis[maxn];
int bac[maxn];
struct node
{
int u;
double d;
int last;
bool operator <(node x)const
{
return d>x.d;
}
};
void dijkstra(int startp)
{
for(int i=0;i<=n+2;i++)
dis[i]=-1;
priority_queue<node> q;
node x;
x.u=startp;
x.d=0;
x.last=0;
q.push(x);
x.u=n+2;
x.d=sqrt((xx[n+1]-xx[n+2])*(xx[n+1]-xx[n+2])+(yy[n+1]-yy[n+2])*(yy[n+1]-yy[n+2]));
x.last=n+1;
q.push(x);
while(!q.empty())
{
node y=q.top();
q.pop();
if(dis[y.u]!=-1)
continue;
dis[y.u]=y.d;
bac[y.u]=y.last;
for(int i=1;i<=n;i++)
{
x.u=i;
x.last=y.u;
if(y.u==n+1)
x.d=y.d+min(abs(xx[n+1]-xx[i]),abs(yy[n+1]-yy[i]))+t;
else
x.d=y.d+t;
q.push(x);
}
if(y.u<=n)
{
x.u=n+2;
x.d=y.d+min(abs(xx[n+2]-xx[y.u]),abs(yy[n+2]-yy[y.u]));
x.last=y.u;
q.push(x);
}
}
}
int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
cin>>n>>t;
cin>>xx[n+1]>>yy[n+1];
cin>>xx[n+2]>>yy[n+2];
for(int i=1;i<=n;i++)
cin>>xx[i]>>yy[i];
dijkstra(n+1);
cout<<dis[n+2]<<endl;
stack<int> s;
s.push(n+2);
while(bac[s.top()])
s.push(bac[s.top()]);
int cnt=0,las=n+1,nx=xx[n+1],ny=yy[n+1];
s.pop();
int cntt=0;
while(!s.empty())
{
int now=s.top();
s.pop();
if(las==n+1)
{
if(now==n+2)
{
nx=xx[n+2],ny=yy[n+2];
cntt++;
}
else if(xx[las]-xx[now]==0||yy[las]-yy[now]==0)
{}
else if(abs(xx[las]-xx[now])<abs(yy[las]-yy[now]))
{
nx=xx[now],ny=yy[las];
cntt++;
}
else
{
nx=xx[las],ny=yy[now];
cntt++;
}
}
else
{
if(now==n+2)
{
if(nx-xx[now]!=0&&ny-yy[now]!=0)
{
if(abs(nx-xx[now])<abs(ny-yy[now]))
{
ny=yy[now];
}
else
{
nx=xx[now];
}
cntt++;
cntt++;
}
else if(xx[las]==xx[now]||yy[las]==yy[now])
{
nx=xx[now];
ny=yy[now];
cntt++;
}
else
{
cntt++;
}
}
else
{
nx=xx[now];
ny=yy[las];
cntt++;
}
}
las=now;
}
cout<<cntt<<endl;
s.push(n+2);
while(bac[s.top()])
s.push(bac[s.top()]);
cnt=0,las=n+1,nx=xx[n+1],ny=yy[n+1];
s.pop();
cntt=0;
while(!s.empty())
{
int now=s.top();
s.pop();
if(las==n+1)
{
if(now==n+2)
{
nx=xx[n+2],ny=yy[n+2];
cout<<0<<' '<<nx<<' '<<ny<<endl;
cntt++;
}
else if(xx[las]-xx[now]==0||yy[las]-yy[now]==0)
{}
else if(abs(xx[las]-xx[now])<abs(yy[las]-yy[now]))
{
nx=xx[now],ny=yy[las];
cout<<0<<' '<<nx<<' '<<ny<<endl;
cntt++;
}
else
{
nx=xx[las],ny=yy[now];
cout<<0<<' '<<nx<<' '<<ny<<endl;
cntt++;
}
}
else
{
if(now==n+2)
{
if(nx-xx[now]!=0&&ny-yy[now]!=0)
{
if(abs(nx-xx[now])<abs(ny-yy[now]))
{
ny=yy[now];
}
else
{
nx=xx[now];
}
cout<<las<<' '<<nx<<' '<<ny<<endl;
cntt++;
cout<<0<<' '<<xx[now]<<' '<<yy[now]<<endl;
cntt++;
}
else if(xx[las]==xx[now]||yy[las]==yy[now])
{
nx=xx[now];
ny=yy[now];
cout<<las<<' '<<nx<<' '<<ny<<endl;
cntt++;
}
else
{
cout<<0<<' '<<xx[now]<<' '<<yy[now]<<endl;
cntt++;
}
}
else
{
nx=xx[now];
ny=yy[las];
cout<<las<<' '<<nx<<' '<<ny<<endl;
cntt++;
}
}
las=now;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3660kb
input:
1 2 1 1 5 3 6 2
output:
4 3 0 1 2 1 5 2 0 5 3
result:
ok correct
Test #2:
score: 0
Accepted
time: 1ms
memory: 3696kb
input:
2 1 1 1 6 1 1 3 6 3
output:
2 2 1 6 3 2 6 1
result:
ok correct
Test #3:
score: 0
Accepted
time: 1ms
memory: 3696kb
input:
0 0 1 1 1 1
output:
0 1 0 1 1
result:
ok correct
Test #4:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
0 0 100 100 0 0
output:
141.421 1 0 0 0
result:
ok correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
1 0 100 100 0 0 100 100
output:
100 2 1 0 100 0 0 0
result:
ok correct
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 3596kb
input:
1 0 100 100 0 0 100 0
output:
0 2 1 0 100 0 0 0
result:
wrong answer step 1: target (0.000000, 100.000000) not on plus (100.000000, 0.000000)