글 읽기 - 케이스 질문 드려요.

leechhe 8년 전 0

정수 범위가 함정인 것 같아서 짰는데... 실패 ㅠㅠ

bfs 구현했는데 구현을 잘못한건가요...

#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>    //priority queue
#include <functional>
#include <cmath>
#include <stack>
#include <iostream>
#include <cstdlib>
#include <limits>
#include <cstring>
#include <map>
using namespace std;
typedef long long ll;
vector<vector<int>> adj;
vector<ll> cost;
const int INF = (1<<31)-1;
int main(){
    int n,m; scanf("%d%d",&n,&m);
    adj = vector<vector<int>> (n+1, vector<int>(n+1,INF));
    cost = vector<ll>(n+1,200000000000);
    for( int i = 0 ; i < m ; ++i ){
        int a,b,c; scanf("%d%d%d",&a,&b,&c);
        adj[a][b] = c;
    }
    int start, dest; scanf("%d%d",&start,&dest);
    
    cost[start] = 0;
    queue<int> q;
    q.push(start);
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        
        for( int next = 1 ; next <= n ; ++next ){
            if( adj[cur][next] == INF ) continue;
            if( cur == next ) continue;
            if( cost[next] > cost[cur] + (ll)adj[cur][next] ){
                cost[next] = cost[cur] + (ll)adj[cur][next];
                q.push(next);
            }
        }
    }
    printf("%lld", cost[dest]);
    return 0;
}

kesakiyo 8년 전 1

bfs로 최단거리를 구할수 있는 경우는 가중치가 없는 그래프에서 가능합니다.

가중치가 있는 트리는 다른 방법을 필요로 하죠

kesakiyo 8년 전 1

트리가 아니라 가중치가 있는 그래프요.

대표적으로 다익스트라 벨만포드 플로이드 이렇게 세가지가 있어요

leechhe 8년 전 0

감사합니다 :)

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

문제

문제

출처

ICPC

케이스 질문 드려요.

leechhe 8년 전 0

kesakiyo 8년 전 1

kesakiyo 8년 전 1

leechhe 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말