srrsr   2년 전


#include <cstdio>
#include <vector>
#include <utility>
using namespace std;
vector < pair<int ,int> > a[20001];
vector < pair<int, int> > s;
vector < int > ans;

void dfs(int v) {
    
    for(int i = 0; i < a[v].size(); i++) {
        s.push_back(make_pair(a[v][i].first, s.empty()? a[v][i].second : s.back().second+a[v][i].second));
        if(ans[s.back().first] > s.back().second) {
            ans[s.back().first] = s.back().second;
        }
        dfs(a[v][i].first);
    }
    s.pop_back();
    return;
}
int main() {
    int v, e, start;
    scanf("%d %d", &v, &e);
    scanf("%d", &start);
    
    for(int i = 0; i < e; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        a[u].push_back(make_pair(v, w));
    }
    for(int i = 0; i <= v; i++) {
        ans.push_back(1000000);
    }
    ans[start] = 0;
    s.push_back(make_pair(start, 0));
    dfs(start);
    for(int i = 1; i <= v; i++) {
        if(ans[i] == 1000000 ) printf("%s\n", "INF");
        else printf("%d\n", ans[i]);
    }
    return 0;
}

kdk8361   2년 전

main 안에 v가 두번 선언되어있네요. 저거때문 아닐까요?

srrsr   2년 전

그건아닌것같아요ㅠㅠ똑같아요바꿔도

kdk8361   2년 전

그게 아니라면 dfs함수를 너무 많이 불러와서 메모리 부족으로 인해 런타임에러가 나오는 것 밖에 생각이 안나네요.

그리고 12번줄에 s.empty()? 할 필요가 있나요? s가 비어있는 경우는 생각이 안나네요.

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