graf1 cpp Defines the entry point for the console application include

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
// graf1.cpp : Defines the entry point for the console application.
//
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define word unsigned int
#include <iostream>
#include <fstream>
using namespace std;
int i, j, n, p, xn, xk;
int flag[11];
unsigned int c[11][11], l[11];
char s[80], path[80][11];
int min(int n)
{
int i, result;
for (i = 0; i < n; i++)
if (!(flag[i])) result = i;
for (i = 0; i < n; i++)
if ((l[result] > l[i]) && (!flag[i])) result = i;
return result;
}
unsigned int minim(unsigned int x, unsigned int y)
{
if (x < y)
return x;
return y;
}
int main()
{
ifstream in("input.txt");
if (!in)
{
cout << "ne mogu otkrit' fail\n";
return 1;
}
in >> n;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) c[i][j] = 0;
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
in >> c[i][j];
for (i = 0; i < n; i++) cout << "x" << i + 1;
cout << endl << endl;
for (i = 0; i < n; i++)
{
printf("x%d", i + 1);
for (j = 0; j < n; j++)
{
printf("%6d", c[i][j]);
c[j][i] = c[i][j];
}
printf("nn\n");
}
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (c[i][j] == 0) c[i][j] = 65535;
in >> xn;
in >> xk;
in.close();
xk--;
xn--;
if (xn == xk)
{
cout << "nachalnaya i konechnaya tichki sovpadayt:" << endl;
getchar();
getchar();
return 0;
}
for (i = 0; i < n; i++)
{
flag[i] = 0;
l[i] = 65535;
}
l[xn] = 0;
flag[xn] = 1;
p = xn;
_itoa_s(xn + 1, s, 10);
for (i = 0; i < n; i++)
{
strcpy_s(path[i], "x");
strcat_s(path[i], s);
}
do
{
for (i = 0; i < n; i++)
if ((c[p][i] != 65535) && (!flag[i]) && (i != p))
{
if (l[i]>l[p] + c[p][i])
{
_itoa_s(i + 1, s, 10);
strcpy_s(path[i + 1], path[p + 1]);
strcat_s(path[i + 1], "-x");
strcat_s(path[i + 1], s);
}
l[i] = minim(l[i], l[p] + c[p][i]);
}
p = min(n);
flag[p] = 1;
} while (p != xk);
if (l[p] != 65535)
{
cout << "put:" << path[p + 1] << endl;
cout << "dlina puti:" << l[p] << endl;
}
else
cout << "takogo puti ne syshestvuet!" << endl;
getchar();
getchar();
return 0;
}