algorithm - 应用 djikstra 改变无向图的权重

Question

如果权重每经过第 k 个距离就不断变化，如何找到从 1 到 n 的最短路径？

给定向量、边和 k 的数量。我们需要找到从 1 到 n 的最短路径。在每第 k 个权重添加到路径之后。我们必须等待 k 秒才能再次移动（因此重量增加了 k，但并非在所有情况下）。

如果我们在旅行时达到第 k 个重量，稍后会看到变化。在旅行时，如果我们达到每个第 k 个值（即 4,8 等），则只会等待 k 时间的剩余部分。例如：k=4 图：1 2 6(uvw), 2 3 4. 我们从 1->2 出发，但在旅行时我们有 4 个，所以我们等待 4 秒（但我们旅行 6-所以 2 秒我们已经在等待）。因此我们只需再等 2 秒，使总重量为 6+2=8，然后我们从 2->3 再次旅行（因为这是最后一次，我们不用担心等待）。

我试图修改 djikstra 但它不正确。

int djikstra(int s,int n,int x,int k)
{
if(s==x) return 0;
for(int i=0;i<MAX;i++) d[i]=INF;

int temp=0;

priority_queue<pii,vector<pii>,greater<pii> > q;

q.push(pii(0,s));
int u,c,v,w;
d[s]=0;
while(!q.empty())
{
    c=q.top().first;
    u=q.top().second;
    q.pop();

    if(d[u]<c) continue;
    if(u==x)
        {return d[u];}

        for(int i=0;i<g[u].size();i++)
        {
            v=g[u][i].first;
            w=g[u][i].second;

            if(d[u]%k==0) temp=0;
            else temp=k-(d[u]%k);

            if(v!=x)
                {

            // cout<<temp<<"\n";
                    if(w<=k)
                    {
                        int we=w;
                        if(temp!=0)
                        {   

                            if(temp<=we)
                                {   we-=temp;
                                    w+=k-(we%k);
                                    temp=0;
                                }
                            else
                            {
                                temp-=w;
                            }
                        }
                        else
                        {
                            if(w%k==0)
                            {
                                w+=k;
                            }
                            else
                            {
                                temp=k-(we%k);
                            }
                        }

                    }
                    else
                    {
                        int wei=w;
                        wei-=temp;

                            if((wei/k)%2!=0)
                            {
                                w+=k-(wei%k);
                                temp=0;

                            }
                            else
                            {
                                if(wei%k==0) temp=0;
                                else temp=k-(wei%k);
                            } 
                    }

                }

            if(d[v] > d[u]+w)
                {
                    d[v]=d[u]+w;
                    q.push(pii(d[v],v));

                }
        }
}

return -1;

}

样品 TC：

Inp:
5(n-no of vertices)
4 (k - kth values)
6 (m- no of edges)
1 2 3 (m 行定义无向边和权重)
1 3 4
2 3 3
3 4 2
4 5 2
3 5 4

输出：
12说明

：

1->3 ( 8 (4 重量 + 4 等待) )
3->5 (4)
8+4=12。

标签： algorithmgraphshortest-path