fork download
copy 
  1. #include <iostream>
  2. #define FIN "salesman.in"
  3. #define BIG 999999
  4. #define DIM 100
  5.  
  6. using namespace std;
  7.  
  8. int matrix[ DIM ][ DIM ], //define adjacency matrix
  9.     explored[ DIM ], //visited array
  10.     nodes; //define a variable that holds the number of the nodes;
  11.  
  12. void readMatrix() {
  13.  
  14.      cin>>nodes;
  15.  
  16.      for(int i = 1; i <= nodes; ++i) {
  17.  
  18.        for(int j = 1; j <= nodes; ++j) {
  19.  
  20.            cin>>matrix[i][j];
  21.        }
  22.      }
  23.  
  24.      cout<<"Adjacency Matrix:\n";
  25.  
  26.      for(int i = 1; i <= nodes; ++i) {
  27.  
  28.        for(int j = 1; j <= nodes; ++j) {
  29.  
  30.            cout<<matrix[i][j]<<" ";
  31.        }
  32.        cout<<endl;
  33.      }
  34.  
  35.      cout<<"\n";
  36. }
  37.  
  38. void greedy() {
  39.  
  40.      int node, start, min, next_node = 1, cost = 0;
  41.  
  42.      for(int peak = 1; peak <= nodes; ++peak) explored[ peak ] = 0;
  43.  
  44.      node = 1;
  45.  
  46.      start = node;
  47.  
  48.      explored[ node ] = 1;
  49.  
  50.      cout<<"Road:\n";
  51.  
  52.      cout<<node<<" ";
  53.  
  54.      for(int i = 1; i <= nodes - 1; ++i) {
  55.  
  56.              min = BIG;
  57.  
  58.              for(int vertice = 1; vertice <= nodes; ++vertice) {
  59.  
  60.                      if(matrix[ node ][ vertice ] != 0 && explored[ vertice ] == 0 && matrix[ node ][ vertice ] < min) {
  61.  
  62.                          min = matrix[ node ][ vertice ];
  63.  
  64.                          next_node = vertice;
  65.                      }
  66.              }
  67.  
  68.              cout<<next_node<<" ";
  69.  
  70.              explored[ next_node ] = 1;
  71.  
  72.              cost = cost + matrix[ node ][ next_node ];
  73.  
  74.              node = next_node;
  75.      }
  76.  
  77.  
  78.      cout<<start;
  79.  
  80.      cost = cost + matrix[ start ][ node ];
  81.  
  82.      cout<<"\nCost = "<<cost<<"\n";
  83. }
  84.  
  85. int main(int argc, char const *argv[]) {
  86.  
  87.   //freopen(FIN, "r", stdin);
  88.  
  89.   readMatrix();
  90.  
  91.   greedy();
  92.  
  93.   return 0;
  94. }
  95.  
Success #stdin #stdout 0.01s 5380KB
comments (?)
stdin
copy 
5
0 1 5 5 3
1 0 2 4 1
5 2 0 6 1
5 4 6 0 9
3 1 1 9 0
stdout
copy 
Adjacency Matrix:
0 1 5 5 3 
1 0 2 4 1 
5 2 0 6 1 
5 4 6 0 9 
3 1 1 9 0 

Road:
1 2 5 3 4 1
Cost = 14
https://ideone.com/5lfvSq
Salesman
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!