Zadanie Przemytnicy c++

Question

Cześć mam problem z zadaniem przemytnicy. Napisałem już kod, który według mnie powinien działać, a na końcu i tak zawsze wypisuje 0. Siedzę nad tym zadaniem już 3 godziny, czy mógłby ktoś mi wytłumaczyć, gdzie popełniłem błąd?
 

#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e4+7;
int dist[2*MAXN];
vector<pair<int,int>> G[2*MAXN];

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

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	for (int i=1; i<=n; i++)
	{
		int number;
		cin>>number;
		G[i].push_back({i+n, number/2});
	}
	
	int m;
	cin>>m;
	
	for (int i=1; i<=m; i++)
	{
		int a, b, c;
		cin>>a>>b>>c;
		G[a].push_back({b, c});
	}
	
	Dijkstra(1);
	cout<<dist[n+1];
	return 0;
}

 

Answer 1

Odpalałeś to w debuggerze, albo np wypisując wszystkie zmienne co drugą linię?

Bo na razie ten kod praktycznie nic nie robi bo:

if (dist[v]<=-d) {
    continue;
}

Na początku dist[START] jest 0 i `d` jest 0, więc kończysz pętlę i od razu wychodzisz z funkcji.

(tbh niezbyt rozumiem o co chodzi z tym minusem)

BTW druga obserwacja na szybko: z tego co rozumiem, opłatę celną zrealizowałeś przez przejście z I do I+N. Ale nigdzie nie widzę żebyś miał krawędzie na tych +N wierzchołkach po których dijkstra mógłby wrócić z powrotem do złota N+1.

Comments

Z minusem chodzi o to, że w kolejce chcę, by wierzchołek mniejszy był pobierany jako pierwszy, więc używam -d , aby go zamienić. Poprawiłem trochę ten kod i stworzyłem nowe połączenia oraz dodałem w kodzie linię fill(dist,dist+2*n+1,1e9);, o której wcześniej zapomniałem, żeby program działał. Teraz już wszystko działa i zadanie wchodzi na 100%, dzięki za pomoc i podpowiedź z tymi nowymi połączeniami :). Poprawiony i działający kod:
 

#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e5+7;
int dist[2*MAXN];
vector<pair<int,int>> G[2*MAXN];

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

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	for (int i=1; i<=n; i++)
	{
		int number;
		cin>>number;
		G[i].push_back({i+n, number/2});
	}
	
	int m;
	cin>>m;
	
	for (int i=1; i<=m; i++)
	{
		int a, b, c;
		cin>>a>>b>>c;
		G[a].push_back({b, c});
		G[a+n].push_back({b+n, c});
	}
	
	Dijkstra(1);
	cout<<dist[n+1];
	return 0;
}