rt,我的代码怎么 AC 的?(确实不知道)能 hack 吗?
#include<bits/stdc++.h>
using namespace std;
struct Side
{
int from;
int to;
int cost;
};
bool cmp(Side a,Side b)
{
if(a.from!=b.from) return a.from<b.from;
return a.to<b.to;
}
struct Svdt
{
int dot;
int val;
int path[52];
bool operator<(const Svdt anth)const
{
return val<anth.val;
}
bool operator>(const Svdt anth)const
{
return val>anth.val;
}
void operator=(const Svdt anth)
{
dot=anth.dot;
val=anth.val;
for(int i=0;i<=51;i++)
path[i]=anth.path[i];
}
}inition;
void swap(Svdt &a,Svdt &b)
{
Svdt t;
t=a,a=b,b=t;
}
Svdt h[4112];
int size;
void initsvdt()
{
inition.dot=0;
inition.val=2147483647;
memset(inition.path,0,sizeof(inition.path));
for(int i=0;i<=4111;i++)
h[i]=inition;
size=0;
}
void ins(Svdt newsvdt)
{
size++;
h[size]=newsvdt;
int npos=size;
while(npos>1)
{
if(h[npos]<h[npos/2])
{
swap(h[npos],h[npos/2]);
npos/=2;
}
else break;
}
}
Svdt top()
{
if(size==0) return inition;
return h[1];
}
void del()
{
if(size==0) return;
h[1]=h[size];
h[size]=inition;
size--;
int npos=1;
while(npos*2<=size)
{
if(h[npos]>h[npos*2]||h[npos]>h[npos*2+1])
{
if(h[npos*2]<h[npos*2+1])
{
swap(h[npos],h[npos*2]);
npos*=2;
}
else
{
swap(h[npos],h[npos*2+1]);
npos*=2,npos++;
}
}
else break;
}
}
int n;
int m;
int sss;
int k;
Side sds[2012];
int sdsbg[52];
int sdscnt[52];
int stpfrom;
int stp[52];
int paths[52][52];
int tmp[52];
int main()
{
ios::sync_with_stdio(0);
cin.tie();
cout.tie();
cin>>n>>m>>k;
sss=1;
m*=2;
for(int i=1;i<=m;i+=2)
{
cin>>sds[i].from>>sds[i].to>>sds[i].cost;
sds[i+1].from=sds[i].to;
sds[i+1].to=sds[i].from;
sds[i+1].cost=sds[i].cost;
}
memset(sdsbg,-1,sizeof(sdsbg));
memset(sdscnt,0,sizeof(sdscnt));
sort(sds+1,sds+m+1,cmp);
int now=0;
for(int i=1;i<=m;i++)
{
if(sds[i].from!=now) now=sds[i].from,sdsbg[sds[i].from]=i,sdscnt[sds[i].from]=1;
else sdscnt[now]++;
}
stpfrom=sss;
for(int i=1;i<=n;i++)
stp[i]=2147483647;
stp[sss]=0;
int okcnt=1;
int nding=sss;
initsvdt();
while(okcnt<n)
{
for(int i=sdsbg[nding],j=1;j<=sdscnt[nding];i++,j++)
{
memset(tmp,0,sizeof(tmp));
for(int j=0;j<=51;j++)
tmp[j]=paths[nding][j];
int inspos=51;
while(inspos>1&&tmp[inspos-1]<sds[i].cost) tmp[inspos]=tmp[inspos-1],inspos--;
tmp[inspos]=sds[i].cost;
int ans=0;
for(int j=1;j<=51;j++)
ans+=((j<=k)?(tmp[j]/2):(tmp[j]));
Svdt instion;
instion.dot=sds[i].to;
instion.val=ans;
for(int j=0;j<=51;j++)
instion.path[j]=tmp[j];
ins(instion);
}
while(1)
{
Svdt nxtnding=top();
if(nxtnding.val==2147483647)
{
okcnt=-okcnt;
break;
}
del();
if(stp[nxtnding.dot]!=2147483647) continue;
stp[nxtnding.dot]=nxtnding.val;
for(int i=0;i<=51;i++)
paths[nxtnding.dot][i]=nxtnding.path[i];
okcnt++;
nding=nxtnding.dot;
break;
}
if(okcnt<0)
{
okcnt=-okcnt;
break;
}
}
cout<<stp[n];
return 0;
}