普通的Dijkstra在松弛的时候进行dp
查看原帖
普通的Dijkstra在松弛的时候进行dp
200011
真的不会编程楼主2023/3/29 21:38

没有用分层图的思想,就是普通的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数据?

2023/3/29 21:38
加载中...