Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <list>
- #include <queue>
- #include <fstream>
- #include <limits>
- #include <algorithm>
- #include <iomanip>
- using namespace std;
- struct node
- {
- int to,
- length;
- node(int _to, int _length)
- {
- to = _to;
- length = _length;
- }
- };
- const int INF = INT_MAX;
- list <node>* graph;
- bool* visited;
- int* dist;
- queue <int> width;
- void dij(int v, int n);
- void print(int n);
- int main()
- {
- const int INF = INT_MAX;
- int n, v, w, l;
- ifstream in("input.txt");
- in >> n;
- graph = new list<node>[n];
- visited = new bool[n];
- dist = new int[n];
- if (in.is_open())
- while (!in.eof())
- {
- in >> v >> w >> l;
- if (--v < n && --w < n)
- graph[v].push_back(node(w, l));
- }
- in.close();
- for (int i = 0; i < n; i++)
- {
- dist[i] = INF;
- visited[i] = false;
- }
- int startV;
- cin >> startV;
- dist[--startV] = 0;
- dij(startV, n);
- system("pause");
- return 0;
- }
- void dij(int v, int n)
- {
- for each (node x in graph[v])
- {
- dist[x.to] = min(dist[x.to], dist[v] + x.length);
- if (!visited[x.to])
- width.push(x.to);
- }
- print(n);
- visited[v] = true;
- if (!width.empty())
- {
- int t = width.front();
- width.pop();
- dij(t, n);
- }
- }
- void print(int n)
- {
- cout << setw(6) << "\nVertex" << setw(6) << "Dist" << endl;
- for (int i = 0; i < n; i++)
- if(dist[i] == INF)
- cout << setw(6) << i + 1 << setw(6) << "INF" << endl;
- else
- cout << setw(6) << i + 1 << setw(6) << dist[i] << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement