글 읽기 - 뭘 틀렸는지 잘 모르겠네요

dlswmd08 5년 전 0

카피닌자식으로 다 따라하고 계속 뭐가틀렸는지 봐도 답이 안나오네요 ..

더군다나 더 이상한건 Dev c++로 그냥 프로그램 돌렸을 때랑 디버깅할때랑 답이 다르네요.

걍 같은 코드인데 디버깅할때랑안할때랑 답이 다른건 도데체 뭔일인건지 정말 울고싶네요.

#include<iostream>
#include<vector>
#include<queue> 
#include<cstring>

using namespace std;

const int INF = 987654321;
const int MAX_V = 500;

typedef pair<int, int> P;
int N, M;

vector<P> adj[MAX_V];
vector<int> trace[MAX_V];
bool visite[MAX_V][MAX_V];

vector<int> Dijk(int start, int vertex)
{
	vector<int> dist(vertex, INF);
	dist[start] = 0;
	
	bool visited[vertex] = {0};
	priority_queue<P, vector<P>, greater<P> > PQ;
	PQ.push(P(0,start));
	
	while(!PQ.empty()){
		int curr;
		int cos;
		do{
			curr = PQ.top().second;
			cos = PQ.top().first;
			PQ.pop();
		}while(!PQ.empty() && visited[curr]);
		
		if(visited[curr]) break;
		
		if(dist[curr] < cos) continue;

		visited[curr] = true;
				
		for(auto &p : adj[curr]){
			int next = p.second, cost = p.first;
			
			if( cost == -1 ) continue;
			
			if(dist[next] > dist[curr] + cost){
				trace[next].clear();
				trace[next].push_back(curr);
				dist[next] = dist[curr] + cost;
				PQ.push(P(dist[next], next));
			}
			else if(dist[next] == dist[curr] + cost){
				trace[next].push_back(curr);
			}
		}
	}
	//printf("%d\n", dist[6]);
	return dist;
}

void Bfs(int destination)
{

	queue<int> q;
	
	q.push(destination);
	while(!q.empty()){
		int curVertex = q.front();
		q.pop();
		
		for(int i=0; i < trace[curVertex].size(); i++){
			
			int neighbor = trace[curVertex][i];
			if(visite[curVertex][neighbor]){
				continue;
			}
			
			for(int i=0; i < adj[neighbor].size(); i++){
				if(adj[neighbor][i].second == curVertex) {
					adj[neighbor][i].first = -1;	
				}
			}
			q.push(neighbor);
		}
	}
}

int main()
{
	
	int S, D;
	while(1){
		memset(visite, false, sizeof(visite));
		memset(trace, 0, sizeof(trace));
		for(int i=0; i < MAX_V; i++){
			adj[i].clear();
		}
		
		scanf("%d%d", &N, &M);
		
		if(N == 0 && M == 0) break;
		
		scanf("%d%d", &S, &D);
	
		for(int i=0; i < M; i++)
		{
			int u, v, p;
			scanf("%d%d%d", &u, &v, &p);
			adj[u].push_back(P(p,v));
		}
		
		Dijk(S, D);
		
		Bfs(D);
		
		vector<int> result = Dijk(S, D);
		
		if(result[D] == INF){
			printf("-1\n");
		}
		else{
			printf("%d\n", result[D]);
		}
	} 
}

djm03178 5년 전 0

목적지 D는 결코 N-1이라는 보장이 없습니다. 그래서 20, 23번째 줄에서 크기를 vertex로 지정하면 목적지보다 큰 인덱스들에 대해서는 전부 배열의 범위를 벗어난 곳에 접근하게 됩니다.

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

문제

문제

출처

ICPC

뭘 틀렸는지 잘 모르겠네요

dlswmd08 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말