[Algorithm] 코딩테스트 치트시트

문자열 자르기

내 블로그

조합

최단경로

다익스트라

• q에서 나갈때 갱신할 떄 continue -> 내 블로그

• q에 들어올때

  /*
  정점 개수 V :
  1 <= V <= 20000
    
  간선 개수 E :
  1 <= E <= 300,000
    
  가중치 / 연결 노드 1 / 연결 노드 1
    
  @@@ 유의사항@@@
  1 부터 시작
  */
    
  #include <iostream>
  #include <vector>
  #include <queue>
    
  #define pii pair<int, int>
  #define INF 6000000001
    
  using namespace std;
    
  inline void srt(int &a, int &b) {
    int temp = (a < b) ? a : b;
    b = (a < b) ? b : a;
    a = temp;
    return;
  }
    
  int main() {
    int V, E;
    cin >> V >> E;
    
    int x;
    cin >> x;
    vector<long long> cost(V+1, INF);
    cost[x] = 0;
      
    vector<vector<int> > adj_list(V+1);
    // 거리는 adj[small][big] 으로
    vector<vector<long long> > adj_mat(V+1, vector<long long>(V+1, INF));
    
    int c, v1, v2;
    for(int i=0; i<E; i++) {
      cin >> c >> v1 >> v2;
      srt(v1, v2);
    
      if(adj_mat[v1][v2] == INF) {
        adj_mat[v1][v2] = c;
        adj_list[v1].push_back(v2);
        adj_list[v2].push_back(v1);
      } else {
        adj_mat[v1][v2] = (c < adj_mat[v1][v2]) ? c : adj_mat[v1][v2];
      }
    }
    
    priority_queue<pii> pq;
    for(int i=0; i<adj_list[x].size(); i++) {
      int v1 = x;
      int v2 = adj_list[x][i];
      srt(v1, v2);
    
      pq.push(make_pair(-adj_mat[v1][v2], adj_list[x][i]));
    }
      
    while(!pq.empty()) {
      pii t = pq.top();
      long long c = -t.first;
      int v = t.second;
      pq.pop();
    
      cost[v] = c;
    
      for(int i=0; i<adj_list[v].size(); i++) {
        if(cost[v] != INF) continue;
    
        int v1 = v;
        int v2 = adj_list[v][i];
        srt(v1, v2);
    
        pq.push(make_pair(-adj_mat[v1][v2], v));
      }
    }
    
    for(int i=1; i<=V; i++) {
      string ans = (cost[i] == INF) ? "INF" : to_string(cost[i]);
      cout << ans << '\n';
    }
    
    return 0;
  }
    
    
    
  

class 정렬

C++ Reference

list

공식문서링크

advance (원형가능)공식문서링크 https://an-thropology.tistory.com/15

문제

백준 1157, 풍선터뜨리기

map

🚩 unordered_map [공식문서] [블로그]

문제 - 내유튜브 참조

🚩 priority_queue [공식문서]