dijkstra.cpp

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;
#define MAX_N  100000

typedef pair<int, int> P;
int n, m;
vector<P> adj[MAX_N];
int deg[MAX_N];
int dist[MAX_N];
bool visited[MAX_N];

struct Order
{
  bool operator()(P const& a, P const& b) const
  {
    return a.second > b.second;
  }
};

void read_input()
{
  scanf("%d %d",&n,&m);
  for(int i=0; i<n; i++) 
  {
    deg[i] = 0;
    dist[i] = -1;
  }

  for(int i=0; i<m; i++) 
  {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w); u--; v--;
    adj[u].push_back(make_pair(v, w));
    adj[v].push_back(make_pair(u, w));
    deg[u]++;
    deg[v]++;
  }
}

void dijkstra(int start)
{
  priority_queue<P, vector<P>, Order> pq;
  
  pq.push(make_pair(start, 0));
  dist[start] = 0;

  while(!pq.empty())
  {
    int u = pq.top().first;
    // printf("pop -> %d %d\n", u, pq.top().second);
    pq.pop();

    for (int i=0; i<deg[u]; i++)
    {
      int v = adj[u][i].first;
      int w = adj[u][i].second;

      if (dist[v] > dist[u] + w || dist[v] == -1) 
      {
        dist[v] = dist[u] + w;
        pq.push(make_pair(v, dist[v])); 
        // printf("push -> %d %d\n", v, dist[v]);
      }
    }
  }

  printf("%d\n", dist[n-1]);
}

int main()
{
  read_input();
  dijkstra(0);
}