Advertisement
Guest User

Untitled

a guest
May 22nd, 2019
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.55 KB | None | 0 0
  1. #include <fstream>
  2. #include <vector>
  3. #include <set>
  4.  
  5. using namespace std;
  6.  
  7.  
  8. class Dijkstra{
  9.     long long* minLength;
  10.     vector<vector<pair<int, short>>> adjList;
  11.     int size;
  12. public:
  13.     ~Dijkstra() {
  14.         delete[] minLength;
  15.     }
  16.     void inputData() {
  17.         ifstream in("input.txt");
  18.         int numberRibs;
  19.         in >> size >> numberRibs;
  20.         minLength = new long long[size];
  21.         for (int i = 0; i < size; i++) {
  22.             minLength[i] = INT64_MAX;
  23.         }
  24.         int u;
  25.         int v;
  26.         short int weight;
  27.         adjList.resize(size);
  28.         for (int i = 0; i < numberRibs; i++) {
  29.             in >> u >> v >> weight;
  30.             if (u != v) {
  31.                 adjList[--u].push_back(pair<int, short>(--v, weight));
  32.                 adjList[v].push_back(pair<int, short>(u, weight));
  33.             }
  34.         }
  35.         in.close();
  36.     }
  37.  
  38.     void dijkstra() {
  39.         minLength[0] = 0;
  40.         set<pair<int, long long>> queue;
  41.         queue.insert(pair<int, long long>(0, 0));
  42.         int curLength;
  43.         int to;
  44.         while (!queue.empty()) {
  45.             int v = (queue.begin())->first;
  46.             queue.erase(queue.begin());
  47.             for (int i = 0; i < adjList[v].size(); i++) {
  48.                 to = adjList[v][i].first;
  49.                 curLength = adjList[v][i].second;
  50.                 if (minLength[v] + curLength < minLength[to]) {
  51.                     queue.erase(pair<int, long long>(to, minLength[to]));
  52.                     minLength[to] = minLength[v] + curLength;
  53.                     queue.insert(pair<int, long long>(to, minLength[to]));
  54.                 }
  55.             }
  56.         }
  57.     }
  58.  
  59.     void writeToFile() {
  60.         ofstream out("output.txt");
  61.         out << minLength[size - 1];
  62.         out.close();
  63.     }
  64.  
  65. };
  66. int main() {
  67.     Dijkstra dijkstra;
  68.     dijkstra.inputData();
  69.     dijkstra.dijkstra();
  70.     dijkstra.writeToFile();
  71.     return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement