Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <cmath>
- #include <sstream>
- using namespace std;
- float cities[130][3];
- float dist[130][130]; ///distance
- float route[130];
- int x, y;
- float nearest_city( float distance[130][130] ) {
- for( int j = 0; j < 130; j++ ) {
- if ( dist[x][j] != 0 && cities[j][2] != 1 ) {
- if ( dist[x][j] < dist[x][y] )
- y = j;
- }
- }
- return y;
- }
- void odleglosci_miedzy_miastami() {
- for( int i = 0; i < 130; i++ ) {
- for( int j = 0; j < 130; j++ ) {
- dist[i][j] = sqrt(pow(cities[j][0] - cities[i][0], 2) + pow(cities[j][1] - cities[i][1], 2));
- }
- }
- }
- int main() {
- float coor_x, coor_y, a;
- float sum = 0.0;
- float sum_help = 100000.0;
- ifstream file;
- file.open("ch130.tsp");
- file >> a;
- int i = 0;
- while( !file.eof() ) {
- file >> a >> coor_x >> coor_y;
- cities[i][0] = coor_x;
- cities[i][1] = coor_y;
- cities[i][2] = 0;
- i++;
- }
- odleglosci_miedzy_miastami();
- for ( int i = 0; i < 130; i++ ) {
- cities[i][2] = 1;
- x = i;
- y = x + 1;
- for ( int k = 0; k < 129; k++ ) {
- nearest_city(dist);
- sum += dist[x][y];
- cities[y][2] = 1;
- x = y;
- for ( int l = 0; l < 130; l++ ) {
- if ( cities[l][2] != 1 )
- y = l;
- }
- }
- sum += dist[x][i];
- for ( int c = 0; c < 130; c++ )
- cities[c][2] = 0;
- route[i] = sum;
- if ( sum < sum_help )
- sum_help = sum;
- sum = 0;
- }
- cout << "Najkrotsza trasa wynosi " << sum_help;
- for ( int z = 0; z < 130; z++ )
- if ( route[z] == sum_help )
- cout << " z miasta nr " << z + 1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement