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 (new)

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

using namespace std;

const int MAX_N = 100010;

int n,m;
vector<int> adj[MAX_N];
vector<int> weights[MAX_N];
int deg[MAX_N];

set<pair<int,int>> Q;

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

int d[MAX_N];
const int INFINITY = 1000000000;
bool explored[MAX_N];
void dijkstra(int s)
{
  for(int u=0; u<n; u++) {
    d[u] = INFINITY;
    explored[u] = false;
  }
  d[0] = 0;
  Q.insert(make_pair(0,s));
  
  while(!Q.empty()) {
    auto pu = *(Q.begin());
    Q.erase(Q.begin());
    int u = pu.second;
    if(explored[u])
      continue;
    
    //cout << u << " " << du << endl;
    explored[u] = true;
    for(int dd=0; dd<deg[u]; dd++) {
      int v = adj[u][dd];
      if(d[v] > d[u] + weights[u][dd]) {
	d[v] = d[u] + weights[u][dd];
	Q.insert(make_pair(d[v],v));
      }
    }
  }
}

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

Fast version (old)

#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;
}