минимальный штрафной путь в взвешенном графике

Рассмотрим неориентированный граф, содержащий N узлов и M ребер. Каждое ребро M i имеет целочисленную стоимость, C i, ассоциируется с ним.

Штраф за путь - это побитовая или каждая реберная стоимость в пути между парой узлов, A и B. Другими словами, если путь содержит ребра M1,М2,..., M k тогда штраф за этот путь равен C1 или C2 ИЛИ ..... Или C k.

Учитывая граф и два узла, A иB , найти путь междуA иB , имеющий минимально возможный штраф, и вывести его штраф; если такой путь не существует, вывести −1, чтобы указать, что нет пути отA доB .

Примечание: петли и множественные ребра являются разрешено.

Ограничения:

1≤N≤103

1≤м≤103

1≤C i

1≤U i,V i≤N

1≤А,B≤N

А≠B

Этот вопрос задается в конкурсе, и его окончание я прошел через учебник, но не смог получить его. может ли кто-нибудь объяснить или дать ответ, как действовать дальше?

3 2
language-agnostic algorithm dynamic-programming

3 ответа:

Его можно решить с помощью динамического программирования, следуя рекурсивной формуле: 

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 - исходный узел.

Идея есть D(v,i) == true тогда и только тогда, когда существует путь от s до v с весом ровно i. Теперь вы итеративно модифицируете график в своем динамическом программировании, пока он не сойдется (что самое большее после итераций n).
это в основном вариант алгоритма Беллмана-Форда. Когда вы закончите создание таблицы DP для решения минимальный путь равен min { x | D(t,x) = true} (где t - целевой узел).

Временная сложность равна O(m*n*log_2(R)), где R - максимальный допустимый вес (1024 в вашем случае).

1

То, что вы ищете, - это алгоритм Дейкстры . Вместо того, чтобы добавлять вес для каждого узла, вы должны его упорядочить.

Таким образом, псевдокод будет выглядеть следующим образом (модифицировано из примера Википедии): 

 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.

0
#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;

}
0