Task: | Lennot |

Sender: | hugo-hur |

Submission time: | 2015-10-06 15:40:04 |

Language: | C++ |

Status: | COMPILE ERROR |

### Compiler report

input/code.cpp: In function 'int minDistance(std::vector<unsigned int>, std::vector<bool>)': input/code.cpp:20:21: error: 'UINT_MAX' was not declared in this scope unsigned int min = UINT_MAX, min_index;//INT_MAX, min_index; ^ input/code.cpp:24:19: error: 'min_index' was not declared in this scope min = dist[v], min_index = v; ^ input/code.cpp:26:9: error: 'min_index' was not declared in this scope return min_index; ^ input/code.cpp: In function 'std::vector<unsigned int> dijkstra(std::vector<std::vector<unsigned int> >, int)': input/code.cpp:50:18: error: 'UINT_MAX' was not declared in this scope dist.push_back(UINT_MAX); sptSet.push_back(false); ^ input/code.cpp:72:48: error: 'INT_MAX' was not declared in this scope if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]){ ^ input/code.cpp: In function 'int minDistance(std::v

### Code

#include <iostream> #include <list> #include <vector> using namespace std; class Flight { public: Flight(unsigned int from, unsigned int to, unsigned int price); unsigned int from, to, price; }; Flight::Flight(unsigned int from, unsigned int to, unsigned int price){ this->from = from; this->to = to; this->price = price; } // Number of vertices in the graph unsigned int V = 4; int minDistance(std::vector<unsigned int> dist, std::vector<bool> sptSet) { // Initialize min value unsigned int min = UINT_MAX, min_index;//INT_MAX, min_index; for (unsigned int v = 0; v < V; v++) if (sptSet[v] == false && dist[v] <= min) min = dist[v], min_index = v; return min_index; } // A utility function to print the constructed distance array /*void printSolution(unsigned int dist[], int n) { std::cout << "Vertex Distance from Source" << std::endl;//printf("Vertex Distance from Source\n"); for (int i = 0; i < V; i++) printf("%d \t\t %d\n", i, dist[i]); }*/ // Funtion that implements Dijkstra's single source shortest path algorithm // for a graph represented using adjacency matrix representation std::vector<unsigned int> dijkstra(vector<vector<unsigned int>> graph/*[V][V]*/, int src) { //unsigned int* dist = new unsigned int[V]; // The output array. dist[i] will hold the shortest std::vector <unsigned int> dist; // distance from src to i //bool* sptSet = new bool[V]; // sptSet[i] will true if vertex i is included in shortest std::vector <bool>sptSet; // path tree or shortest distance from src to i is finalized // Initialize all distances as INFINITE and stpSet[] as false for (unsigned int i = 0; i < V; i++){ dist.push_back(UINT_MAX); sptSet.push_back(false); }//dist[i] = INT_MAX, sptSet[i] = false; // Distance of source vertex from itself is always 0 dist[src] = 0; // Find shortest path for all vertices for (unsigned int count = 0; count < V - 1; count++) { // Pick the minimum distance vertex from the set of vertices not // yet processed. u is always equal to src in first iteration. int u = minDistance(dist, sptSet); // Mark the picked vertex as processed sptSet[u] = true; // Update dist value of the adjacent vertices of the picked vertex. for (unsigned int v = 0; v < V; v++) // Update dist[v] only if is not in sptSet, there is an edge from // u to v, and total weight of path from src to v through u is // smaller than current value of dist[v] if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]){ dist[v] = dist[u]; if (v % 2 != 0){//Every other flight is free dist[v] += graph[u][v]; } //dist[v] = dist[u] + graph[u][v]; } } // print the constructed distance array //printSolution(dist, V); //delete[] dist; //delete[] sptSet; return dist; } /*unsigned int** createMatrix(std::vector <Flight> flights){ //unsigned int* matrix = new unsigned int[3]; //unsigned int** matrix2 = new unsigned int*[flights.size()]; //matrix2 }*/ vector<vector<unsigned int>> createGraph(vector<Flight> flights, unsigned int n){ unsigned int v = n;//flights.size(); vector<vector<unsigned int>> graph; for (unsigned int i = 0; i < v; i++){ //unsigned int* p = new unsigned int[v]; graph.push_back(vector<unsigned int>()); for (unsigned int z = 0; z < v; z++){ graph.back().push_back(0); } } //Arrange flights by "from" //For all flights with start point of 1 check the price to dest for (Flight f : flights){ graph[f.from - 1][f.to - 1] = f.price; } return graph; } // Driver program to test methods of graph class int main() { /* Let us create the example graph discussed above */ //Price as a distance unsigned int n = 0; unsigned int m = 0; cin >> n; cin >> m; V = n; vector<Flight> flights; for (unsigned int i = 0; i < m; i++){ unsigned int from, to, price; cin >> from >> to >> price; flights.push_back(Flight(from, to, price)); } //cin >> V; //vector<Flight> flights; //flights.push_back(Flight(1, n, 100)); //flights.push_back(Flight(1, 2, 10)); //flights.push_back(Flight(2, n, 10)); vector<vector<unsigned int>> graph = createGraph(flights, n); //graph[0][1] = 3; //graph[0][2] = 5; //graph[1][0] = 2; //{ 0, 0, 0, 9, 0, 10, 0, 0, 0 }, //{ 0, 0, 4, 0, 10, 0, 2, 0, 0 }, //{ 0, 0, 0, 14, 0, 2, 0, 1, 6 }, //{ 8, 11, 0, 0, 0, 0, 1, 0, 7 }, //{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } unsigned int price = dijkstra(graph, 0).back(); std::cout << price << std::endl; return 0; }