dijkstra.cpp

/*
 * =====================================================================================
 *
 *       Filename:  IA_dijkstra.cpp
 *
 *    Description: http://www.infoarena.ro/problema/dijkstra
                   Graful este orientat.
 *
 *        Version:  1.0
 *        Created:  06/21/2015 13:13:34
 *       Revision:  none
 *       Compiler:  gcc/g++
 *
 *         Author:  Marius-Constantin Melemciuc
 *          email:
 *   Organization:
 *
 * =====================================================================================
 */
  
#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <queue>
#include <climits>
  
using namespace std;
  
vector<vector<pair<int, int> > > graph;
  
class Cmp {
public:
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
        return (a.second > b.second)? true: false;
    }
};

// O(MlogN)
vector<int> dijkstra(int source, int n, int m) {
    vector<int> distance(n + 1, INT_MAX);
    vector<bool> visited(n + 1, false);
    priority_queue<pair<int, int>,
                   vector<pair<int, int> >,
                   Cmp> pq;
  
    distance[source] = 0;
    pq.push(make_pair(source, distance[source]));
  
    while (!pq.empty()) {
        int x  = pq.top().first;
         
        pq.pop();
         
        if (visited[x])
            continue;
        visited[x] = true;
          
        for (auto it = graph[x].begin(); it != graph[x].end(); it++) {
            int y    = it->first;
            int cost = it->second;
  
            if (distance[y] > distance[x] + cost) {
  
                distance[y] = distance[x] + cost;
                pq.push(make_pair(y, distance[y]));
            } /* if */
        } /* for */
    } /* while */
  
    return distance;
}
  
int main() {
    int n, m;
      
    ifstream input("dijkstra.in");
    ofstream output("dijkstra.out");
  
    input >> n >> m;
      
    vector<pair<int, int> > row;
    for (int i = 0; i <= n; i++)
        graph.push_back(row);
  
    for (int i = 0; i < m; i++) {
        int x, y, cost;
  
        input >> x >> y >> cost;
        graph[x].push_back(make_pair(y, cost)); // oriented graph
    }
  
    vector<int> distance = dijkstra(1, n, m);
  
    for (int i = 2; i <= n; i++) {
        output << (distance[i] == INT_MAX? 0: distance[i]) << ' ';
    }
    output << '\n';
     
    input.close();
    output.close();
  
    return 0;
}