能否这样实现多关键字最短路？

一条边的权值由

k

个属性定义，比较优先级从高到低依次为

w_1,w_2,\cdots,w_k

。

那么，按照这个算法流程是否能正确求出最短路？假设源点为

s

，总共

n

个点。

注意，这里的小根堆的比较规则只关心第一关键字

CPP

定义一个用来存储节点的小根堆 pq，最短路的第一关键字最小的节点为堆顶。
定义 bool 数组 vis，大小为 n，初始默认全 0。
定义数组 dis，大小为 n，存储每个点的最短路。
pq.push(s)
dis[s] 的所有属性等于 0，因为是出发点
while(!pq.empty()){
    int u=pq.top();
    pq.pop();
    if(vis[u])continue;
    vis[u]=1;
    扫描所有 u 连接的点 v，令边权为 weight{
        if(dis[v].w[1] > dis[u].w[1]+weight){
            dis[v].w[1]=dis[u].w[1]+weight;
            dis[v] 的 w[2],w[3],.... 等属性赋值为 dis[u] 的。
            q.push(v)
        }else if(dis[v].w[1]==dis[u].w[1]+weight){
            dis[v] 的 w[2],w[3],.... 等属性与 dis[u] 的取 min，比较规则仍然按照一开始说的。
        }
    }
}

本意就是模拟 dijkstra 算法，但是没这么写过，故来洛谷问问。

换个说法，就是松弛过程中，

v

的最短路第一关键字可以用

u

的最短路更新的情况下，先更新第一关键字，然后

v

的其他关键字直接复制为

u

的。

否则，如果

v

的最短路第一关键字等于

u

的最短路的第一关键字。那么

v

的其他关键字打包，与为

u

的其他关键字打包的结果取 min。

换个人话，就是令

v

的原来最短路的第二个关键字及以后组成

(p_2,p_3,\cdots,p_k)

，

u

的最短路的第二个关键字及以后组成

(q_2,q_3,\cdots,q_k)

，用后缀对前者取 min。

另外，如果这个不对，那么，它是否在第一关键字，或者所有的关键字边权都只有

1

的情况下正确？

能否这样实现多关键字最短路？

讨论操作

回复

相关推荐

能否这样实现多关键字最短路？