没有用分层图的思想,就是普通的Dijkstra在松弛的时候进行dp,但也只有 WA 9 ,这种思想是否可行?
核心代码:
void dij(int x)
{
memset(dis,0x3f,sizeof(dis));
priority_queue<node> q;
dis[x][0]=0;
q.push(node{dis[x][0],x});
while(!q.empty())
{
node x=q.top();q.pop();
if(vis[x.id]) continue;
vis[x.id]=1;
for(int i=0;i<g[x.id].size();i++)
{
int v=g[x.id][i],t=val[x.id][i];
if(dis[v][0]>dis[x.id][0]+val[x.id][i])
{
dis[v][0]=dis[x.id][0]+val[x.id][i];
q.push(node{dis[v][0],v});
for(int j=1;j<=k;j++)
dis[v][j]=min(dis[v][j],min(dis[x.id][j]+val[x.id][i],dis[x.id][j-1]));
}
}
}
}
有没有小范围的hack数据?