글 읽기 - C++ 50% 시간초과

minstar 2년 전 0

dfs 두번 돌려서 풀었는데 계속 50퍼에서 시간초과가 납니다. 실수한 부분이 있을까요?

#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;

int v, max_val;
vector<pair<int, int>> tree[100010];
bool visited[100010];

int dfs(int s)
{
    stack<pair<int, int>> stck;
    int node;

    stck.push({s, 0});
    visited[s]=true;
    while(!stck.empty()){
        int idx=stck.top().first;
        int val=stck.top().second;
        stck.pop();
        bool flag=false;
        for(int i=0; i<tree[idx].size(); i++){
            if(!visited[tree[idx][i].first]){
                flag=true;
                visited[tree[idx][i].first]=true;
                stck.push({idx, val});
                stck.push({tree[idx][i].first, val+tree[idx][i].second});
                break;
            }
        }
        if(!flag){
            if(val>max_val){
                node=idx;
                max_val=val;
            }
        }
    }
    return node;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin>>v;
    for(int i=0; i<v; i++){
        int v1, v2, val; cin>>v1;
        while(cin>>v2 && v2!=-1){
            cin>>val;
            tree[v1].push_back({v2, val});
            tree[v2].push_back({v1, val});
        }
    }
    int s=dfs(1);
    max_val=0;
    memset(visited, false, sizeof(visited));
    dfs(s);
    cout<<max_val;
    return 0;
}

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

문제

문제

출처

ICPC

C++ 50% 시간초과

minstar 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말