graph.cpp

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)

#define DESC(class, type) class<type> *, vector<class<type> *>, greater<class<type> *> 

using namespace std;
static const int nil = (1 << 31);
static const int inf = (1 << 30);

class UnionFind {
private:
  vector<int> arr;

public:
  UnionFind(int size) : arr(size, -1) {}
  int root(int node) {
    return arr[node] < 0 ? node : arr[node] = root(arr[node]);
  }
  int size(int x) { return -arr[root(x)]; }
  bool unionSet(int x, int y) {
    x = root(x);
    y = root(y);
    if (x != y) {
      if (arr[x] < arr[y])
        swap(x, y);
      arr[x] += arr[y];
      arr[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) { return root(x) == root(y); }
};

template <typename T>
class Edge;

template <typename T> class Vertex {
public:
  int idx;
  int color = nil;
  int dist = inf;

  vector<Edge<T>* > dists;
  int size() { return dists.size(); }
  Vertex(int idx):idx(idx){}
  bool operator==(const Vertex *o) { return dist == o->dist; }
  bool operator!=(const Vertex *o) { return dist != o->dist; }
  bool operator>(const Vertex *o) { return dist > o->dist; }
  bool operator>=(const Vertex *o) { return dist >= o->dist; }
  bool operator<(const Vertex *o) { return dist < o->dist; }
  bool operator<=(const Vertex *o) { return dist <= o->dist; }
};
template <typename T>
ostream &operator<<(ostream &os, Vertex<T>& v){
    os << "Vert: " << v.idx << ", dist = " << v.dist;
    os << ", connect=[";
    for(Edge<T> *u: v.dists){
      os << u->to->idx << ", ";
    }
    os << "]";
    return os;
}

template <typename T> class Edge{
  public:
    Vertex<T> *from;
    Vertex<T> *to;
    T weight;
    Edge(Vertex<T> *from, Vertex<T> *to, T weight)
    :from(from), to(to), weight(weight){}



  bool operator==(const Edge *o) { return weight == o->weight; }
  bool operator!=(const Edge *o) { return weight != o->weight; }
  bool operator>(const  Edge *o) { return weight >  o->weight; }
  bool operator>=(const Edge *o) { return weight >= o->weight; }
  bool operator<(const  Edge *o) { return weight <  o->weight; }
  bool operator<=(const Edge *o) { return weight <= o->weight; }
};
template <typename T>
ostream &operator<<(ostream &os, Edge<T>& e){
  os << "Edge: " << e.from->idx << "(" << e.from->dist << ") -> ";
  os << e.to->idx << "(" << e.to->dist << "), weight = " << e.weight;
  return os;
}

template <typename T> class Graph {
public:
  vector<Vertex<T> *> V;
  vector<Edge<T> *> E;
  Vertex<T> *p_root = new Vertex<T>(-1);
  Graph(int v_size) {
    for (int i = 0; i < v_size; i++) {
      auto v = new Vertex<T>(i);
      V.push_back(v);
    }
    p_root->dist = 0;
  }

  Vertex<T> *getVertex(int idx) { return V[idx]; }

  int getColor(int idx) { return V[idx]->param; }

  int size() { return V.size(); }

  void colorize(int idx, int color) { V[idx]->param = color; }

  void colorize(Vertex<T> *vertex, int color) { vertex->param = color; }

  bool isColorize(int idx, int color) {
    if (V[idx]->param == nil)
      return false;
    V[idx]->param = color;
    return true;
  }

  Vertex<T>* dfs(Vertex<T>* p, Vertex<T>* v){
    Vertex<T> *r = new Vertex<T>(*v);
    r->dist = 0;
    stateInit(0);
    for(Edge<T>* e : v->dists){
      if(e->to->idx != p->idx){
        Vertex<T> *t = dfs(v, e->to);
        t->dist += e->weight;
        if(r->dist < t->dist){
          r = t;
        }
      }
    }
    return r;
  }
  T diameter(){
    Vertex<T> *r = dfs(p_root, getVertex(0));
    Vertex<T> *t = dfs(p_root, r);
    return t->dist;
  }

  void unite(int v1, int v2, T weight = 1) {
    Edge<T> *e1 = new Edge<T>(V[v1], V[v2], weight);
    Edge<T> *e2 = new Edge<T>(V[v2], V[v1], weight);

    E.push_back(e1);
    E.push_back(e2);
    V[v1]->dists.push_back(e1);
    V[v2]->dists.push_back(e2);
  }

  void arrow(int v_from, int v_to, T weight = 1) {
    Edge<T> *e = new Edge<T>(V[v_from], V[v_to], weight);
    E.push_back(e);
    V[v_from]->dists.push_back(e);
  }

  void dijkstra(int idx) {
    stateInit();
    priority_queue<DESC(Vertex, T) > pq;
    Vertex<T> *s = V[idx];
    s->dist = 0;
    pq.push(s);
    while (!pq.empty()) {
      Vertex<T> *v = pq.top();
      pq.pop();
      for (Edge<T> *e : v->dists) {
        if (e->to->dist > e->from->dist + e->weight) {
          e->to->dist = e->from->dist + e->weight;
          pq.push(e->to);
        }
      }
    }
  }
  void bellmanford(int idx) {
    stateInit();
    Vertex<T> *s = getVertex(idx);
    s->dist = 0;
    while (true) {
      bool update = false;
      for (Edge<T>* e : E) {
        if (e->from->dist != inf && e->to->dist > e->from->dist + e->weight) {
          e->to->dist = e->from->dist + e->weight;
          update = true;
        }
      }
      if (!update)
        break;
    }
  }

  T kruskal() {
    stateInit();
    sort(E.begin(), E.end(), [](Edge<T> *e1, Edge<T> *e2) { return e1->weight < e2->weight; });
    UnionFind uf = UnionFind(size());
    int res = 0;
    for (Edge<T>* e : E) {
      if (!uf.findSet(e->from->idx, e->to->idx)) {
        uf.unionSet(e->from->idx, e->to->idx);
        res += e->weight;
      }
    }
    return res;
  }

  void stateInit(T init=inf) {
    for (Vertex<T>* v : V) {
      v->dist = init;
      v->color = nil;
    }
  }
};

int main() {
  int N, E, s;
  cin >> N >> E >> s;
  Graph<int> *g = new Graph<int>(N);
  for (int i = 0; i < E; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    g->unite(a, b, c);
  }
  g->dijkstra(s);
  cout << g->getVertex(N-1)->dist << endl;

  return 0;
}