Zadanie Bug - potyczki algorytmiczne

Question

Cześć, ogólnie to robię zadanie Bug : https://szkopul.edu.pl/problemset/problem/wh8bZRITUAHN9t6ZvJdhNkAa/site/?key=statement i ten kod wchodzi na 60 pkt, nie mam pojęcia dlaczego.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 4e5 + 7;
vector<pair<int,int>> graph[MAXN];
int dist[MAXN];
int n,m;

void Dijkstra(int start){
    fill(dist,dist + 2*n + 1,1e9);
    priority_queue<pair<int,int>> Q;
    Q.push({start,0});
    while(Q.size()){
        auto [v,w] = Q.top();
        Q.pop();
        if(-w >= dist[v])
            continue;
        dist[v] = -w;
        
        for(auto [u,d] : graph[v]){
            if(dist[u] > dist[v] + d)
                Q.push({u,-(dist[v] + d)});
        }
    }
}

void add_edge(int a,int b,int w){
    graph[a].push_back({b,w});
    graph[b].push_back({a,w});
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin >> n >> m;

    for(int i=0;i<m;++i){
        int a,b,w;
        cin >> a >> b >> w;

        if(w & 1){
            add_edge(a,b + n,w);
            add_edge(a + n,b,w);
        }
        else{
            add_edge(a,b,w);
            add_edge(a+n,b+n,w);
        }
    }

    Dijkstra(1);
    if(dist[2 * n] == 1e9)
        cout << "0\n";
    else
        cout << dist[2 * n] << '\n';
    return 0;
}

 

Comments

Może priority_queue zabiera za dużo pamięci. Spróbuj podmienić to na set. Wtedy w linii 24. możesz dodatkowo usuwać stary wpis dla wierzchołka u

Answer 1

Masz błąd w algorytmie dijkstra

Zamiast - (dist[v] + d), powinieneś użyć - (dist[v] - d).

if (dist[u] > dist[v] - d)
    Q.push({u, -(dist[v] - d)});

:) 
 

Comments

Wydaje mi sie, że powinno być jednak - (dist[v] + d)

---

Uzasadnij?

---

struct Edge {
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w) {}
};

const int MAXN = 2e5 + 5;
vector<Edge> graph[MAXN];
int dist[MAXN];
int n, m;

void Dijkstra(int start) {
    fill(dist, dist + 2 * n + 1, 1e9);
    priority_queue<pair<int, int>> Q;
    Q.push({0, start});
    dist[start] = 0;

    while (!Q.empty()) {
        auto [w, v] = Q.top();
        Q.pop();
        w = -w; // Negacja, ponieważ kolejka priorytetowa ma domyślny porządek malejący.
        if (w > dist[v])
            continue;

        for (const auto& edge : graph[v]) {
            int u = edge.to;
            int d = edge.weight;
            if (dist[u] > dist[v] + d) {
                dist[u] = dist[v] + d;
                Q.push({-dist[u], u});
            }
        }
    }
}

void add_edge(int a, int b, int w) {
    graph[a].emplace_back(b, w);
}

Jedynie co mi przychodzi żeby dostało to 100pkt Jeszce to powyższy kod

---

W kodzie wyżej napisałeś dist[v] + d zamiast dist[v] - d, więc zgaduje, ze ta wersja jest poprawna

---

Ten kod może już teoretycznie przejść na 100, bo ostatnio dostawało 60 przez TLE i zbyt duże zużycie pamięci.

---

@Whistleroosh, my bad :) masz racje