글 읽기 - 런타임 에러?

iljimae 7년 전 0

단순히 다익스트라 알고리즘을 돌려봤는데 테스트 케이스는 맞게 나오는데 자꾸 런타임 에러가 뜹니다 ㅠㅠ 감이 안잡히는데 좀 도와주세요

// Applying dijkstra's algorithm on string nodes.  
#include <iostream> 
#include <cstdlib> 
#include <cstdio> 
#include <cstring> 
#include <algorithm> 
#include <map> 
#include <set> 
#include <vector> 
#include <queue> 
#include <assert.h> 
#include <string> 
#include <sstream> 
#include <utility> 
using namespace std;  

#define INF 987654321

// for getting input 
int n;  
vector<string> a[33];   
map<string,int> id;   
map<int,string> name;  
string start,goal;  

// for implementing dijkstra's algorithm 
struct edge {int to,cost;};  
typedef pair<int,int> P;  // stores (minimum distance,node number) 
vector<edge> G[32*31];  
int d[32*31]; 
int previous[32*31];  

void dijkstra(int s){
	priority_queue< P,vector<P>,greater<P> > que;  
	fill(d+1,d+32*31,INF);  
	memset(previous,-1,sizeof(previous));  
	d[s] = 0;  
	que.push(P(d[s],s));  
	while (!que.empty()){
		P p = que.top(); que.pop(); 
		int v = p.second;  
		if (d[v] < p.first) continue;  
		for (int i = 0; i < G[v].size(); i++){
			edge e = G[v][i];  
			if (d[e.to] > d[v]+e.cost){
				d[e.to] = d[v]+e.cost;  
				que.push(P(d[e.to],e.to));  
				previous[e.to] = v;  
			}
		}
	}
}

vector<int> pathReconstruction(int t){
	vector<int> path;  
	for (; t != -1; t = previous[t]){
		path.push_back(t);  
	}
	reverse(path.begin(),path.end()); 
	return path;  
}

int main(){
	cin >> n;  
	cin.ignore(); 
	for (int i = 0; i < n; i++){
		string input;  
		getline(cin,input);  
		istringstream iss(input);  
		string word;  
		while (iss >> word){
			a[i].push_back(word);  
		}
	}
	cin >> start >> goal; 
	int make_id = 1;  
	// create an id for each string, then also create a map that returns the string for each id. 
	for (int i = 0; i < n; i++){
		for (int j = 0; j < a[i].size(); j++){
			if (!id[a[j][i]]){ 
				name[make_id] = a[j][i];  
				id[a[j][i]] = make_id++;
			} 
		}
	}
	// fill up connectivity in G 
	for (int i = 0; i < n; i++){
		int from = id[a[i][0]];  
		for (int j = 1; j < a[i].size(); j++){
			int to = id[a[i][j]];  
			edge e; 
			e.to = to, e.cost = 1; 
			G[from].push_back(e); 
			// because the graph is bi-directional. 
			e.to = from;  
			G[to].push_back(e);   
		}
	}
	dijkstra(id[start]);  
	if (d[id[goal]] == INF){ // dijkstra's algorithm returns INF if there is no route from start to goal. 
		cout << "no route found" << endl; 
	}else{
		vector<int> path = pathReconstruction(id[goal]);  
		for (int i = 0; i < path.size(); i++){
			cout << name[path[i]] << " ";  
		}
		cout << endl; 
	}
	return 0;  
}

iljimae 7년 전 0

자문자답: 일단 줄 80-82 i,j위치 바꿔야하고 path 의 크기가 1보다 작거나 같은지 확인해주는 조건문이 있어야 합니다. 이것들을 고치고 나니 accept 받았어요.

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

문제

문제

출처

ICPC

런타임 에러?

iljimae 7년 전 0

iljimae 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말