글 읽기 - vector 문법 질문입니다

lyzqm 7년 전 0

vector<pair<int, int>> vec[10001];

형태의 vector가 있는데 현재지점에서 다음지점으로 이동시킬 때

vec[curr]값을 vector<pair<int, int>> edge로 받고 연산했을 때(성공)랑

vec[curr]값을 vec[curr][i] 형태로 바로 사용할때 (실패)가 값이 다른데 왜 이런지 아시는 분 있나요?

//성공
while (!q.empty()){
		int curr = q.front().first;
		int w = q.front().second;
		vector<pair<int, int>> edge = vec[curr];
		q.pop();

		for (int i = 0; i < edge.size(); i++){
			int next = edge[i].first;

			if (w < edge[i].second) edge[i].second = w;

			if (ans[next] < edge[i].second){
				ans[next] = edge[i].second;
				q.push(make_pair(next, edge[i].second));
			}
		}
	}

//실패
while (!q.empty()){
		int curr = q.front().first;
		int w = q.front().second;
		q.pop();

		for (int i = 0; i < vec[curr].size(); i++){
			int next = vec[curr][i].first;

			if (w < vec[curr][i].second) vec[curr][i].second = w;

			if (ans[next] < vec[curr][i].second){
				ans[next] = vec[curr][i].second;
				q.push(make_pair(next, vec[curr][i].second));
			}
		}
	}

lyzqm 7년 전 0

1939 중량제한 성공한 소스는 다음과같고 위에 언급한 부분만 다릅니다.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 1111111111
int N, M ,S, E;
vector<pair<int, int>> vec[10001];
int ans[10001];
void bfs(){
	queue<pair<int, int> > q;
	q.push({ S, INF });
	ans[S] = INF;
	while (!q.empty()){
		int curr = q.front().first;
		int w = q.front().second;
		vector<pair<int, int>> edge = vec[curr];
		q.pop();

		for (int i = 0; i < edge.size(); i++){
			int next = edge[i].first;

			if (w < edge[i].second) edge[i].second = w;

			if (ans[next] < edge[i].second){
				ans[next] = edge[i].second;
				q.push(make_pair(next, edge[i].second));
			}
		}
	}
}
int main(){
	scanf("%d%d", &N, &M);	
	for (int m = 0; m < M; m++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		vec[a].push_back({ b, c });
		vec[b].push_back({ a, c });
	}
	scanf("%d%d", &S, &E);
	
	bfs();
	printf("%d\n", ans[E]);
	return 0;
}

gallopsys 7년 전 1

std::vector class의 문법 문제기 보다는 value copy & reference의 개념으로 접근해보셔야 할 거 같습니다.

vector<pair<int, int>> edge = vec[curr];의 경우에는 vector<pair<int, int>> 자료형이 edge 변수로 복사되는 것입니다. 즉, 다시 말해 원본의 값이 변하지 않는다는 소리입니다.

이 선언을 vector<pair<int, int>> edge = vec[curr]; 대신에 vector<pair<int, int>> &edge = vec[curr];라고 하면 WA를 받겠죠...

성공한 소스는 복사의 개념이라면, 밑에 소스는 왜 실패했는지 아실 수 있으실 거라 믿습니다.

lyzqm 7년 전 0

아 감사합니다

알고리즘상 원본값을 바꿔야되는건줄 알았는데 아니였네요

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

문제

문제

출처

ICPC

vector 문법 질문입니다

lyzqm 7년 전 0

lyzqm 7년 전 0

gallopsys 7년 전 1

lyzqm 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말