Algo lab/dijkstra

Slower version

#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 1000010;

vector<int> adj[MAX_N];
vector<int> weights[MAX_N];

int n,m;
int deg[MAX_N];
void read_input()
{
  cin >> n >> m;
  for(int i=0; i<n; i++) {
    deg[i] = 0;
  }
  
  for(int i=0; i<m; i++) {
    int a,b,w;
    
    cin >> a >> b >> w;
    a--; b--;

    adj[a].push_back(b);
    weights[a].push_back(w);
    deg[a]++;

    adj[b].push_back(a);
    weights[b].push_back(w);
    deg[b]++;
  }
}

bool is_visited[MAX_N];
int D[MAX_N];
const int INFINITY = 1000000000;

void dijkstra(int s)
{
  for(int i=0; i<n; i++) {
    is_visited[i] = false;
    D[i] = INFINITY;
  }

  D[s] = 0;

  for(int i=0; i<n; i++) {
    // find u with minimum D[u] such that is_visited[u] = false
    int u = -1;
    int du = INFINITY;
    for(int x=0; x<n; x++) {
      if((!is_visited[x]) && (D[x] < du)) {
	u = x;
	du = D[x];
      }
    }

    //cout << u << " - " << du << endl;

    for(int j=0; j<deg[u]; j++) {
      int v = adj[u][j];  // edge (u,v)
      int w = weights[u][j];

      //cout << D[u] << " " << w << " " << D[v] << endl;
      if(D[u] + w < D[v]) {
	D[v] = D[u] + w;
      }
    }
    is_visited[u] = true;
  }

}

int main()
{
  read_input();
  dijkstra(0);
  cout << D[n-1] << endl;
}

Fast version

#include <iostream>
#include <vector>
#include <set>

using namespace std;

const int MAX_N = 1000010;

vector<int> adj[MAX_N];
vector<int> weights[MAX_N];

int n,m;
int deg[MAX_N];
void read_input()
{
  cin >> n >> m;
  for(int i=0; i<n; i++) {
    deg[i] = 0;
  }
  
  for(int i=0; i<m; i++) {
    int a,b,w;
    
    cin >> a >> b >> w;
    a--; b--;

    adj[a].push_back(b);
    weights[a].push_back(w);
    deg[a]++;

    adj[b].push_back(a);
    weights[b].push_back(w);
    deg[b]++;
  }
}

bool is_visited[MAX_N];
int D[MAX_N];
const int INFINITY = 1000000000;

void dijkstra(int s)
{
  for(int i=0; i<n; i++) {
    is_visited[i] = false;
    D[i] = INFINITY;
  }

  D[s] = 0;
  set<pair<int,int>> Q;
  Q.insert(make_pair(0,s));
  
  for(int i=0; i<n; i++) {
    int u;

    do {
      if(Q.empty())
	return;
      pair<int,int> uu = *(Q.begin());
      Q.erase(Q.begin());
      u = uu.second;
    } while(is_visited[u]);

    for(int j=0; j<deg[u]; j++) {
      int v = adj[u][j];  // edge (u,v)
      int w = weights[u][j];

      //cout << D[u] << " " << w << " " << D[v] << endl;
      if(D[u] + w < D[v]) {
	D[v] = D[u] + w;

	Q.insert(make_pair(D[v],v));
      }
    }
    is_visited[u] = true;
  }

}

int main()
{
  read_input();
  dijkstra(0);
  cout << D[n-1] << endl;
}