글 읽기 - (1948 임계경로) 런타임 에러가 뜨는데 어디가 문제인지 잘 안 보입니다 ㅠㅠ

gangmuk 5년 전 0

위상정렬 알고리즘으로 간단하게 짰는데, 메모리 초과도 아니고 런타임에러가 뜨네요...

간단하게 짰다고 생각해서 그런지 어디가 문제가 되서 런타임에러가 뜨는지 보이지 않습니다 ㅠㅠ

새로운 눈으로 보고 찝어주실 수 있을까요?

미리 감사합니다!!

(알고리즘)

최대 시간을 계산하기 위한 adjacent_graph 와 도로 갯수를 계산하기 위해 거꾸로 연결된 adjacent_reverse_graph 백터를 만들어서 구했습니다.

최대 거리를 계산하고 도착 도시부터 다시 bfs로 큐를 써서 각 연결된 도시까지 거리를 뺐을 때 그 연결된 도시까지 최대시간과(최대 거리를 계산할때 이미 계산됨) 같으면 도로++해서 출력하는 방식 입니다.

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

struct edge{
    int to;
    int local_time;
};

queue<int> q, q2;
int indegree[10001];
int total_time[10001];
vector<edge> adj[10001];
vector<edge> adj_reverse[10001];

int main(){
    int c;  //number of cities
    int r;  //number of roads
    cin>>c>>r;
    int from, to, taken;
    for(int i=1; i<=r; i++){
        cin>>from>>to>>taken;
        edge temp_edge;
        temp_edge.to = to;
        temp_edge.local_time = taken;
        adj[from].push_back(temp_edge);
        temp_edge.to = from;
        temp_edge.local_time = taken;
        adj_reverse[to].push_back(temp_edge);
        indegree[to]++;
        total_time[to] = taken;
    }
    int start, end;
    cin>>start>>end;

    for(int i=1; i<=c; i++){
        if(indegree[i] == 0){
            q.push(i);
        }
    }

    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for(int i=0; i<adj[cur].size(); i++){
            int next_city = adj[cur][i].to;
            int time_to_next_city = adj[cur][i].local_time;
            if(total_time[next_city] > total_time[cur]+time_to_next_city){
                //do nothing
            }
            else{
                total_time[next_city] = total_time[cur]+time_to_next_city;
            }
            indegree[next_city]--;
            if(indegree[next_city] == 0)
                q.push(next_city);
        }
    }

    cout<<total_time[end]<<endl;

    int ans2 = 0;

    q2.push(end);
    while(!q2.empty()){
        int cur = q2.front();
        q2.pop();
        for(int i=0; i<adj_reverse[cur].size(); i++){
            int t = adj_reverse[cur][i].local_time;
            if(total_time[cur] - t == total_time[adj_reverse[cur][i].to]){
                q2.push(adj_reverse[cur][i].to);
                ans2++;
            }
        }
    }
    cout<<ans2<<endl;
    return 1;
}

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

문제

문제

출처

ICPC

(1948 임계경로) 런타임 에러가 뜨는데 어디가 문제인지 잘 안 보입니다 ㅠㅠ

gangmuk 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말