글 읽기 - 틀렸습니다

mwy3055 5년 전 0

다익스트라를 수행해서, 최단경로에 포함된 간선을 모두 지운 후, 다시 다익스트라를 수행하는 코드입니다.

어째서인지 런타임 에러를 받았습니다. 조언 부탁드립니다.

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
using namespace std;

typedef pair<int, int> Pair;		//거리, 목적지
typedef vector<Pair>::iterator p_iterator;
const int INF = 0x7f000000;

bool find(vector<Pair>& adj, p_iterator& it, int dest)
{
	if (adj.empty())
		return false;

	for (it = adj.begin(); it != adj.end(); it++)
	{
		if ((*it).second == dest)
			return true;
	}
	return false;
}
void deleteEdge(vector<vector<Pair>>& adj, queue<int> q, int* dist, int n)
{
	vector<pair<int, p_iterator>> deleteList;
	while (!q.empty())
	{
		int search = q.front();
		q.pop();
		for (int i = 0; i < n; i++)
		{
			if (i == search) continue;
			p_iterator t;
			//간선이 존재하고 그 간선이 최단거리의 일부이면
			if (find(adj[i], t, search) && (dist[search] == dist[i] + (*t).first))
			{
				deleteList.push_back({ i,t });
				q.push(i);
			}
		}
	}
	for (pair<int, p_iterator> t : deleteList)
		adj[t.first].erase(t.second);
}
void dijk(int n, int s, int d, vector<vector<Pair>>& adj, queue<int> q) 
{
	//최단경로 다익스트라->간선 삭제
	int* dist = new int[n];
	fill(dist, dist + n, INF);
	dist[s] = 0;
	
	priority_queue<Pair, vector<Pair>, greater<Pair>> pq;

	pq.push({ 0,s });	
	while (!pq.empty())
	{
		Pair now = pq.top();
		int search = now.second;
		pq.pop();
		for (Pair t : adj[search])
		{
			int scost = t.first, sidx = t.second;
			int& old = dist[sidx], renew = dist[search] + t.first;
			if (renew < old)
			{
				old = renew;
				pq.push({ renew, sidx });
			}
		}
	}

	q.push(d);
	deleteEdge(adj, q, dist, n);

	delete[] dist;
}

int dijk(int n, int s, int d, vector<vector<Pair>> adj)
{
	//거의 최단 경로 다익스트라
	int* dist = new int[n];
	fill(dist, dist + n, INF);
	dist[s] = 0;

	priority_queue<Pair, vector<Pair>, greater<Pair>> pq;

	pq.push({ 0,s });
	while (!pq.empty())
	{
		Pair now = pq.top();
		int search = now.second;
		pq.pop();
		for (Pair t : adj[search])
		{
			int scost = t.first, sidx = t.second;
			int& old = dist[sidx], renew = dist[search] + t.first;
			if (renew < old)
			{
				old = renew;
				pq.push({ renew, sidx });
			}
		}
	}

	int rtn = dist[d];
	delete[] dist;
	return rtn;
}

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

	while (true)
	{
		int n, m, s, d;
		cin >> n >> m;
		if (n == 0) return 0;

		cin >> s >> d;

		vector<vector<Pair>> adjList;
		for (int i = 0; i < n; i++)
			adjList.push_back(vector<Pair>());
		for (int i = 0; i < m; i++)
		{
			int u, v, p;
			cin >> u >> v >> p;
			adjList[u].push_back({ p,v });
		}

		queue<int> q;
		dijk(n, s, d, adjList, q);
		int almost = dijk(n, s, d, adjList);
		cout << ((almost == INF) ? -1 : almost) << '\n';
	}
}

djm03178 5년 전 1

하나의 벡터에서 어떤 원소가 erase 되면 기존에 그 벡터에 대한 iterator들은 모두 무효화됩니다. 이는 벡터에서 어떤 원소를 지우는 연산이 그 뒤의 모든 원소들을 전부 한 칸씩 당겨오는 연산을 포함하고 있댜는 것을 생각하면 확연합니다. 그래서 하나의 벡터에 대해 기존에 얻어놓은 iterator를 여러 개 지워서는 안 됩니다.

mwy3055 5년 전 0

그럼 저장하지 말고 찾을 때마다 지워야겠네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀렸습니다

mwy3055 5년 전 0

djm03178 5년 전 1

mwy3055 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말