Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <vector>
- #include <set>
- using namespace std;
- class Dijkstra{
- long long* minLength;
- vector<vector<pair<int, short>>> adjList;
- int size;
- public:
- ~Dijkstra() {
- delete[] minLength;
- }
- void inputData() {
- ifstream in("input.txt");
- int numberRibs;
- in >> size >> numberRibs;
- minLength = new long long[size];
- for (int i = 0; i < size; i++) {
- minLength[i] = INT64_MAX;
- }
- int u;
- int v;
- short int weight;
- adjList.resize(size);
- for (int i = 0; i < numberRibs; i++) {
- in >> u >> v >> weight;
- if (u != v) {
- adjList[--u].push_back(pair<int, short>(--v, weight));
- adjList[v].push_back(pair<int, short>(u, weight));
- }
- }
- in.close();
- }
- void dijkstra() {
- minLength[0] = 0;
- set<pair<int, long long>> queue;
- queue.insert(pair<int, long long>(0, 0));
- int curLength;
- int to;
- while (!queue.empty()) {
- int v = (queue.begin())->first;
- queue.erase(queue.begin());
- for (int i = 0; i < adjList[v].size(); i++) {
- to = adjList[v][i].first;
- curLength = adjList[v][i].second;
- if (minLength[v] + curLength < minLength[to]) {
- queue.erase(pair<int, long long>(to, minLength[to]));
- minLength[to] = minLength[v] + curLength;
- queue.insert(pair<int, long long>(to, minLength[to]));
- }
- }
- }
- }
- void writeToFile() {
- ofstream out("output.txt");
- out << minLength[size - 1];
- out.close();
- }
- };
- int main() {
- Dijkstra dijkstra;
- dijkstra.inputData();
- dijkstra.dijkstra();
- dijkstra.writeToFile();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement