[5w] MST, 최단거리

MST란?

reference
백준문제 : 백준 1647
아이디어

코드

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;
int N, M; //집의 개수, 길의 개수
unordered_map<int, int> head;  //집의 번호들이 1부터 순차적 증가할거란 보장이 없음, 즉 집이 100개있다고 집 번호가 101번이 없다는 보장이 없음

struct Edge{
    int a,b,weight;
};
struct cmp{
    bool operator()(Edge first, Edge second){
        return first.weight>second.weight;
    }
};
int findHead(int node){
    if(node==head[node]) return node;
    return findHead(head[node]);
}
Edge makeE(int a,int b,int weight){
    Edge edge;
    edge.a=a;
    edge.b=b;
    edge.weight=weight;
    return edge;
}
bool checkHead(Edge edge){  //합칠수 있으면 true반환
    if(findHead(edge.a)==findHead(edge.b)) return false;
    else return true;
}
void mergeNode(Edge edge){
    int aHead=findHead(edge.a);
    int bHead=findHead(edge.b);
    if(aHead<bHead) head[bHead]=aHead;
    else head[aHead]=bHead;
}
int main(){
    cin>>N>>M;
    priority_queue<Edge, vector<Edge>, cmp> pq;

    for(int i=0;i<M;i++){
        int a,b,c;
        cin>>a>>b>>c;
        head[a]=a;
        head[b]=b;
        Edge edge=makeE(a,b,c);
        pq.push(edge);
    }
    int edgeCnt=0; //N-1개 연결되면 끝
    int result=0;
    while(!pq.empty()){
        Edge nowEdge=pq.top();
        pq.pop();
        if(checkHead(nowEdge)) {
            mergeNode(nowEdge);
            edgeCnt++;
            if(edgeCnt==N-1){
                cout<<result;
                return 0;            
            }
            result+=nowEdge.weight;
        }
    }
    return 0;
}

최단거리란?

reference
백준문제 : 백준 1504
아이디어

코드

#include <iostream>
#include <vector>
#include <queue>
#define INT_MAX 987654321

using namespace std;

struct Edge {
    int to, weight;
};

int N, E, mustA, mustB;
vector<vector<Edge>> edges;

vector<int> dijkstra(int start) {
    vector<int> dist(N + 1, INT_MAX);
    vector<bool> visited(N+1, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        int currentDist = pq.top().first;
        int currentNode = pq.top().second;
        pq.pop();
        if(visited[currentNode]) continue;
        visited[currentNode]=true;
        for (const Edge& edge : edges[currentNode]) {
            int nextNode = edge.to;
            int nextDist = currentDist + edge.weight;

            if (nextDist < dist[nextNode]) {
                dist[nextNode] = nextDist;
                pq.push({nextDist, nextNode});
            }
        }
    }

    return dist;
}

int main() {
    cin >> N >> E;
    edges.resize(N + 1);

    for (int i = 0; i < E; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        edges[a].push_back({b, c});
        edges[b].push_back({a, c});
    }
    cin >> mustA >> mustB;

    vector<int> distFrom1 = dijkstra(1);
    vector<int> distFromA = dijkstra(mustA);
    vector<int> distFromB = dijkstra(mustB);

    
    int path1 = distFrom1[mustA] != INT_MAX && distFromA[mustB] != INT_MAX && distFromB[N] != INT_MAX ? 
                distFrom1[mustA] + distFromA[mustB] + distFromB[N] : INT_MAX;
 
    int path2 = distFrom1[mustB] != INT_MAX && distFromB[mustA] != INT_MAX && distFromA[N] != INT_MAX ? 
                distFrom1[mustB] + distFromB[mustA] + distFromA[N] : INT_MAX;

    int result = min(path1, path2);
    if (result == INT_MAX) {
        cout << -1;
    } else {
        cout << result;
    }

    return 0;
}