分层图(图解+例题) |
您所在的位置：网站首页 › PSD分层大图是什么意思 › 分层图(图解+例题) |
分层图(图解+例题)
|
分层图
分层图多用于求最短路径,但是最短路径中可以有k条边的权值为0。 既然可以k条边为0,那么对于k条边的选取就是个问题。 所以有了分层图的概念。 对于每个点都可以选择下一条边是否赋予权值为0,那么我们就可以将图画出k+1层。 图例我们简单画一下一个有向图,并且k=1(有一条边权值可以为0)
我们模拟从0开始,0可以走的路路径 我们可以看到,如果走同一层,那么权值就要+5或这+100,如果向上一层走那么要加上权值0,并且k减减,也就是每次移动可以消耗免费次数和不消耗免费次数这两种情况可以选择! 那么剩下的情况大家可以手动画一下。 代码实现我们可以将dis数组开成二维dis[i][j]表示到达i号结点,用了j次免费操作! 比如dis[2][0]表示到达2号结点,没有用免费操作,也就是在第一层图移动。 比如dis[2][3],到达2号结点用了3次免费操作,那么下一次移动应该在第3/4层图进行! 注意理解上述操作! 接下来是一道例题,大家可以动手完成。(我用的是dijkstra+优先队列优化,完成k次免费的最短路径问题) 飞行路线 #include using namespace std; const int maxn=1e4+10; int dis[maxn][15],vis[maxn][15],head[maxn]; int n,m,k,sum; int start,last; struct node { int id,v,used;//used使用了几次免费券 node() {} node(int id,int v,int used):id(id),v(v),used(used) {} bool operator int to,next,w; } edge[maxn memset(dis,0x7f7f7f7f,sizeof(dis)); priority_queue q; q.push(node(start,0,0)); dis[start][0]=0; while(!q.empty()) { node t=q.top(); q.pop(); int u=t.id; int kk=t.used; if(vis[u][kk])continue; vis[u][kk]=1; for(int i=head[u]; i; i=edge[i].next) { int v=edge[i].to; int w=edge[i].w; //两种情况,用免费和不用免费 //不用 if(dis[v][kk]>dis[u][kk]+w) { dis[v][kk]=dis[u][kk]+w; q.push(node(v,dis[v][kk],kk)); } //用免费券 if(kk+1dis[u][kk]+0) { dis[v][kk+1]=dis[u][kk]; q.push(node(v,dis[v][kk+1],kk+1)); } } } } int main() { scanf("%d%d%d",&n,&m,&k); scanf("%d%d",&start,&last); for(int i=1; i ans=min(ans,dis[last][i]); } printf("%d\n",ans); return 0; }如果对你有帮助多多点赞支持! |
(这是初始情况,接下来我们分层) k=1,我们要分k+1层
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |