[백준 1916번 C/C++] 최소비용 구하기

 

백준 1916번 C/C++] 최소비용 구하기

 

 

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

---

 

 

해결전략

 

Dijkstra Algorithm (다익스트라 알고리즘)

---

 

코드

 

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

int n, m, result;
int ch[1001];

struct Edge {
    int e;
    int cost;
    Edge(int a, int b) {
        e = a;
        cost = b;
    }
    bool operator<(const Edge& b)const {
        return cost > b.cost;
    }
};

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

    priority_queue<Edge> Q;
    vector<pair<int, int>> graph[1001];

    cin >> n >> m;

    //dist[] 벡터배열은 시작지점에서 도착지점까지의 최소비용을 담는다.
    //시작 지점이 start일 때 도착지점 1, 2, 3,..., n까지의 최소비용을 각각 담는다.
    vector<int> dist(n + 1, 2147000000);//최대값을 기본값으로 세팅.

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back(make_pair(b, c));
    }

    int start, end;
    cin >> start >> end;

    //시작위치에서는 cost를 0으로 시작.
    Q.push(Edge(start, 0));
    dist[start] = 0;

    while (!Q.empty())
    {
        int now = Q.top().e;
        int cost = Q.top().cost;

        Q.pop();

        //새로 구한 최소비용이 기존의 최소비용 보다 크다면 갱신하지 않고 continue;
        if (cost > dist[now]) continue;

        //기
        for (int i = 0; i < graph[now].size(); i++)
        {
            //다음 도시 방문
            int next = graph[now][i].first;
            int nextCost = cost + graph[now][i].second;

            //방문 도시까지의 최소비용이 dist[방문도시]보다 작다면 dist[방문도시] 갱신.
            if (dist[next] > nextCost)
            {
                dist[next] = nextCost;
                Q.push(Edge(next, nextCost));//Q에 삽입
            }
        }
    }

    cout << dist[end];

    return 0;
}

 

 

---

 

 

유사문제

 

80번

https://designerd.tistory.com/entry/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-7680%EB%B2%88-%EA%B7%B8%EB%9E%98%ED%94%84-DFS-BFS-%EA%B4%80%EB%A0%A8-%EB%B3%B4%EC%B6%A9%EB%AC%B8%EC%A0%9C#80._%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[코딩테스트] 76~80번 그래프, DFS, BFS 관련 보충문제

 

 

---

 

 

 

 

다른 시도들

 

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

int n, m, start, dest, MinCost=2147000000;
vector<vector<int>> city;
int ch[1001];

struct Edge {
    int go;
    int stop;
    int cost;
    Edge(int a, int b, int c) {
        go = a;
        stop = b;
        cost = c;
    }
    bool operator<(const Edge& b)const {
        return stop < b.stop;
    }
    bool operator<(const Edge& c)const {
        return cost < c.cost;
    }
};

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

    priority_queue<Edge> Q;
    vector<Edge> graph;

    cin >> n >> m;
    city.resize(m + 1, vector<int>(m + 1));
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph.push_back(Edge(a, b, c));
    }

    Q.push(Edge(1, 0, 0));
    dist[] = 0;

    while (!Q.empty())
    {
        int now = Q.top().go;
        int c
    }
    

    return 0;
}

 

 

 

 

 

 

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

int n, m, start, dest, MinCost=2147000000;
vector<vector<int>> city;
int ch[1001];

void DFS(int go, int sum)
{
    if (go == dest) 
    {
        if (MinCost > sum) MinCost = sum;
        
        return;
    }

    for (auto& i : city[go])
    {
        if (city[go][i] != 0 && ch[go] == 0)
        {
            for (int i = 0; i < city[go].size(); i++)
            {
                ch[go] = 1;
                DFS(i, sum + city[go][i]);
                ch[go] = 0;
            }
        }
    }

}

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

    cin >> n >> m;
    city.resize(m + 1, vector<int>(m + 1));
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        city[a][b] = c;
    }
    
    cin >> start >> dest;

    for (auto j : city[start])
    {
        cout << j << " ";
    }

    ch[start] = 1;
    DFS(start, 0);

    cout << MinCost;

    return 0;
}