Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <vector>
- int intMax = 4000;
- using namespace std;
- vector<int> dijkstra(int n, int startPoint, vector<vector<int>> &w) {
- vector<bool> visited(n);
- vector<int> distance(n);
- for (int i = 0; i < n; i++) {
- distance[i] = w[startPoint][i];
- visited[i] = false;
- }
- distance[startPoint] = 0;
- int index = 0, u;
- for (int i = 0; i < n; i++) {
- int minDistance = intMax;
- for (int j = 0; j < n; j++) {
- if (!visited[j] and distance[j] != -1 and distance[j] < minDistance) {
- minDistance = distance[j];
- index = j;
- }
- }
- u = index;
- visited[u] = true;
- for (int j = 0; j < n; j++) {
- if (!visited[j] and w[u][j] != -1 and distance[u] != -1 and (distance[u] + w[u][j] < distance[j])) {
- distance[j] = distance[u] + w[u][j];
- }
- }
- }
- return distance;
- }
- int main() {
- ifstream fin("input.txt");
- ofstream fout("output.txt");
- int vertices, wayValueCount, startFrom;
- fin >> vertices >> wayValueCount >> startFrom;
- startFrom--;
- vector<vector<int>> w(vertices, vector<int>(vertices, intMax));
- for (int i = 0; i < wayValueCount; i++) {
- int from, to, value;
- fin >> from >> to >> value;
- from--, to--;
- w[from][to] = value;
- }
- vector<int> dist;
- dist = dijkstra(vertices, startFrom, w);
- for (int i = 0; i < vertices; i++) {
- if (dist[i] != intMax)
- fout << dist[i] << ' ';
- else
- fout << "-1 ";
- }
- }
Add Comment
Please, Sign In to add comment