加权图中的最小惩罚路径

Question

考虑包含 N 个节点和 M 个边的无向图。每条边M_i都有一个整数成本，C_i，与之相关联。

路径的惩罚是一对节点A和B之间路径中每条边成本的按位或.换句话说，如果路径包含边 M₁,M₂,...,M_k 那么这条路径的惩罚是 C₁ 或 C₂ 或 ... 或 C_k.

给定一个图和两个节点，A和B，找到A[=78=之间的路径] 和 B 有最小可能的惩罚并打印它的惩罚；如果不存在这样的路径，打印−1表示不存在从A到B.

的路径
注意：允许循环和多边。

限制条件：

1≤N≤10³

1≤M≤10³

1≤C_i<1024

1≤U_i,V_i≤N

1≤A,B≤N

A≠B

这个问题是在一个竞赛中提出的，它已经结束了我浏览了教程但无法理解。谁能解释或给出答案如何进行？

Answer 1

可以按照递归公式使用动态规划求解：

D(s,0) = true
D(v,i) = false OR D(v,i) OR { D(u,j) | (u,v) is an edge, j or c(u,v) = i }

其中s是源节点。

当且仅当存在从 s 到 v 的路径且权重恰好为 i 时，这个想法是 D(v,i) == true。
现在，您在动态规划中迭代修改图形，直到它收敛（最多在 n 次迭代之后）。
这基本上是 Bellman-Ford algorithm 的变体。完成为解决方案创建 DP table 后，最小路径为 min { x | D(t,x) = true}（其中 t 是目标节点）。

时间复杂度为 O(m*n*log_2(R))，其中 R 是允许的最大权重（在您的情况下为 1024）。

Answer 2

您要找的是Dijkstra's Algorithm。与其为每个节点添加权重，不如对其进行 ORing。

因此，伪代码如下（根据维基百科示例修改）：

 1  function Dijkstra(Graph, source):
 2
 3      create vertex set Q
 4
 5      for each vertex v in Graph:             // Initialization
 6          dist[v] ← INFINITY                  // Unknown distance from source to v
 7          prev[v] ← UNDEFINED                 // Previous node in optimal path from source
 8          add v to Q                          // All nodes initially in Q (unvisited nodes)
 9
10      dist[source] ← 0                        // Distance from source to source
11      
12      while Q is not empty:
13          u ← vertex in Q with min dist[u]    // Source node will be selected first
14          remove u from Q 
15          
16          for each neighbor v of u:           // where v is still in Q.
17              alt ← dist[u] OR length(u, v)
18              if alt < dist[v]:               // A shorter path to v has been found
19                  dist[v] ← alt 
20                  prev[v] ← u 
21
22      return dist[], prev[]

注意第 17 行的 OR。

Answer 3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll,ll > pr;
vector <pr> adj[10005];
bool visited[10005][10005];
int main(){
    ll n,m;
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=m;i++){
        ll u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        adj[u].push_back(make_pair(v,w));
        adj[v].push_back(make_pair(u,w));
    }
    ll source,destination;
    scanf("%lld%lld",&source,&destination);
    queue<ll> bfsq;
    bfsq.push(source);// source into queue
    bfsq.push(0);// 
    while(!bfsq.empty()){
    ll u=bfsq.front();
        bfsq.pop();
        ll cost=bfsq.front();
        bfsq.pop();
        visited[u][cost]=true;
        for(ll i=0;i<adj[u].size();i++){
          ll  v=adj[u][i].first;// neighbor of u is v
          ll  w2=adj[u][i].second;//// u is connected to v with this cost
          if(visited[v][w2|cost]==false){
            visited[v][w2|cost]=true;
            bfsq.push(v);
            bfsq.push(w2|cost);


          }
        }
    }
    ll ans=-1LL;
    for(ll i=0;i<1024;i++){
        if(visited[destination][i]==true){
            ans=i;
            break;
        }
    }
    printf("%lld\n",ans);
    return 0;

}

加权图中的最小惩罚路径

minimum penalty path in weighted graph

language-agnostic

algorithm

graph

dynamic-programming