0 / 0 / 0
Регистрация: 03.04.2012
Сообщений: 4
1

Работа с графом.Найти кратчайший маршрут между двумя вершинами.

04.04.2012, 18:53. Показов 10003. Ответов 4
Метки нет (Все метки)

Между некоторыми деревнями края Васюки ходят автобусы. Поскольку пассажиропотоки здесь не очень большие, то автобусы ходят всего несколько раз в день.
Марии Ивановне требуется добраться из деревни d в деревню v как можно быстрее (считается, что в момент времени 0 она находится в деревне d).
Формат входных данных:
Во входном файле записано число N - общее число деревень (1 <= N <= 100), номера деревень d и v, затем количество автобусных рейсов R (0 <= R <= 10000). Затем идут описания автобусных рейсов. Каждый рейс задается номером деревни отправления, временем отправления, деревней назначения и временем прибытия (все времена - целые от 0 до 10000). Если в момент t пассажир приезжает в какую-то деревню, то уехать из нее он может в любой момент времени, начиная с t.
Формат выходных данных:
В выходной файл вывести минимальное время, когда Мария Ивановна может оказаться в деревне v. Во второй строке показать номера рейсов, с помощью которых она может там оказаться. Если она не сможет с помощью указанных автобусных рейсов добраться из d в v, вывести -1.
Пример
input.txt output.txt
3 5
1 3 1-2-3
4
1 0 2 5
1 1 2 3
2 3 3 5
1 1 3 10

Добавлено через 1 час 57 минут
Я что-то пытался сделать не работает...
Pascal
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
program individ_5;
 
type
   refnode = ^node;
   refarc = ^arc;
   node = record
      id: integer;
      next: refnode;
      arclist: refarc;
   end;
   arc = record
      st_t: integer;
      fin_t: integer;
      adj: refnode;
      next: refarc;
   end;
   farray = array[1..10000] of boolean;
 
var
   g, v1, v2: refnode;
   n, m1, m2, sum, sum1, min: integer;
   visited: farray;
   s, ssum: string;
 
function search(i: integer; q: refnode): refnode;
begin
   while (q^.id <> i) and (q <> nil)  do
      q := q^.next;
   search := q;
end;
 
procedure CreateGraph(var g: refnode; var n, m1, m2: integer);
var
   f: text;
   a: refarc;
   i, m, err, v1, v2, t1, t2: integer;
   z, z1, q, head: refnode;
   s: string;
begin
   assign(f, 'input08.txt');
   reset(f);
   if seekeof(f) then writeln('Файл пуст')
   else begin
      readln(f, s);
      Val(s, n, err);
      if err = 0 then begin
         new(head);
         head^.id := 1;
         head^.next := nil;
         head^.arclist := nil;
         g := head;
         for i := 2 to n do 
         begin
            new(q);
            q^.id := i;
            q^.next := nil;
            q^.arclist := nil;
            g^.next := q;
            g := q;
         end;
         g := head;
         readln(f, m1, m2);
         readln(f, m);
         for i := 1 to m do 
         begin
            readln(f, v1, t1, v2, t2);
            z := search(v1, head);
            z1 := search(v2, head);
            new(a);
            a^.st_t := t1;
            a^.fin_t := t2;
            a^.next := z^.arclist;
            z^.arclist := a;
            z^.arclist^.adj := z1;
         end;
         
         g := head;
      end;
   end;
   close(f);
end;
 
procedure brows(g: refnode);
var
   a: refarc;
   nn, na: integer;
begin
   nn := 0;
   na := 0;
   while g <> nil do 
   begin
      writeln('Вершина ', g^.id);
      writeln('Список дуг');
      a := g^.arclist;
      if a = nil then writeln('пуст');
      while a <> nil do 
      begin
         writeln('Дуга к вершине ', (a^.adj)^.id, ' начальное время ', a^.st_t, ' конечное время ', a^.fin_t);
         inc(na);
         a := a^.next;
      end;
      inc(nn);
      g := g^.next;
   end;
   writeln('В графе ', nn, ' вершин ', na, ' дуг');
end;
 
procedure bb(v1, v2: refnode; var s, ssum: string; var sum: integer; var sum1: integer; var min: integer);
var
   a: refarc;
   s1: string;
   i: integer;
begin
   if v1 <> v2 then begin
      a := v1^.arclist;
      while a <> nil do 
      begin
         write(a^.adj^.id<>m1);
         if (a^.st_t >= sum) and (a^.adj^.id<>m1) then begin
            sum1 := sum;
            sum := a^.fin_t;
            str(a^.adj^.id, s1);
            s := s + s1 + '-';
            bb(a^.adj, v2, s, ssum, sum, sum1, min);
            delete(s, length(s), 1);
            i := length(s);
            while s[i] <> '-' do 
            begin
               delete(s, length(s), 1);
               dec(i);
            end;
            sum := sum1;
         end;
         a := a^.next;
      end;
   end
   else if sum < min then begin
      min := sum; 
      ssum := s; 
      delete(ssum, length(s), 1);
   end;
end;
 
begin
   creategraph(g, n, m1, m2);
   brows(g);
   v1 := search(m1, g);
   v2 := search(m2, g);
   visited[m1] := true;
   sum1 := 0;
   min := maxint;
   str(m1, s);
   s := s + '-';
   bb(v1, v2, s, ssum, sum, sum1, min);
  // if min=maxint then writeln('-1')
  // else 
   writeln(min,' ' ,ssum);
end.
не работает..помогите пожалуйста

Добавлено через 3 часа 29 минут
Написал прогу но он ищет от первой вершины до конечной, помогите переписать так, чтобы она с заданной вершины искала
Pascal
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
const
  maxn = 100;
  maxt = 10000;
  inf = maxint div 2;
type
  station = record
      ns:integer;
      time:longint;
  end;
  bus = record
        n:integer;
        st:array[1..maxn]of station;
        end;
 
var
   m,n,b,e,e1,i:integer;
   tr:array[1..maxt]of bus;
   time:array[0..maxn]of longint;
   ok:array[0..maxn]of boolean;
 
procedure readdata;
var
 i,j:integer;
begin
  assign(input,'input09.txt');
  reset(input);
  read(n,b,e,m);
 // b:=1;
  for i:=1 to m do
    begin
      tr[i].n:=2;
      for j:=1 to tr[i].n do
        read(tr[i].st[j].ns, tr[i].st[j].time);
    end;
  close(input);
end;
 
procedure writedata;
begin
  assign(output,'b.out');
  rewrite(output);
  writeln(time[e]);
  close(output);
  writeln(time[e]);
end;
 
procedure update(st:byte);
var
 i,j,k:byte;
begin
  ok[st]:=true;
  for i:=1 to m do
    for j:=1 to tr[i].n do
       if (tr[i].st[j].ns = st) and (tr[i].st[j].time >= time[st]) then
         for k:= j+1 to tr[i].n do
           if tr[i].st[k].time < time[tr[i].st[k].ns] then
              time[tr[i].st[k].ns] := tr[i].st[k].time;
 
end;
 
procedure solve;
var
 i,min:byte;
 f:boolean;
begin
  for i:=0 to n do
    begin
      time[i] := inf;
      ok[i] := false;
    end;
  time[b] := 0;
  f:=true;
  while not ok[e] and f do
     begin
       min :=0;
       for i:=1 to n do
         if not ok[i] then
            if time[i] < time[min] then min := i;
       if min < 1 then f:=false;
       update(min);
     end;
  if not ok[e] then time[e] := -1;
 
end;
 
begin
  readdata;
  solve;
  writedata;
end.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
04.04.2012, 18:53
Ответы с готовыми решениями:

Найти кратчайший путь между двумя заданными городами
Дана плоская страна и в ней n городов. Предположим, что в этой стране есть дорожная сеть. Найти...

В неориентированном графе требуется найти минимальный путь между двумя вершинами
Путь В неориентированном графе требуется найти минимальный путь между двумя вершинами. ...

Найти кратчайший маршрут, и указать последовательности торговых точек. Графы
Условие: Программа должна найти длину кратчайшего маршрута, но и указать последовательность...

Найти кратчайший маршрут, начинающийся в 1-м городе и проходящий через все остальные города
Имеется n городов. Некоторые из них соединены дорогами известной длины. Вся система дорог задана...

4
Эксперт С++
4725 / 2546 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
04.04.2012, 19:15 2
Pascal
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
var 
a: array[1..100,1..4] of integer; 
num, time, res: array[1..100] of integer;
mas_kontr: array[1..100] of boolean;
n, d, v, r, i, min, t: integer;
begin
read(n,d,v,r);
for i:=1 to r do
read(a[i][1], a[i][2], a[i][3], a[i][4]);
for i:=1 to n do
time[i]:=2000000;
time[d]:=0;
while true do
begin
min:=0;
for i:=1 to n do
if (mas_kontr[i]=false) and (time[i]<>2000000) then
begin
if min=0 then min:=i
else
  if time[i]<time[min] then min:=i;
end;
if min=0 then break;
for i:=1 to r do
if a[i][1]=min then
begin
  if (mas_kontr[a[i][3]]=false) and (a[i][2]>=time[min]) and (time[i]>a[i][4]) then
  begin 
  time[i]:=a[i][4];
  num[i]:=min;
  end;  
end;
mas_kontr[min]:=true;
end;
if time[v]=2000000 then writeln(-1)
else
begin
writeln(time[v]);
t:=v;
n:=1;
while(t>0) do
begin
res[n]:=t;
t:=num[t];
inc(n);
end;
for i:=n-1 downto 1 do
write(res[i],' ');
writeln;
end;
end.
0
0 / 0 / 0
Регистрация: 03.04.2012
Сообщений: 4
04.04.2012, 20:27  [ТС] 3
valeriikozlov, спасибо большое) но программа, которую вы написали, накрылась на тестах

Конкретно на тесте 'input3.txt' . Выдает не минимальный вес.
Вместо '2' выдает '17.

Можете ли вы переписать программу? Спасибо большое заранее.
Вложения
Тип файла: txt INPUT03.TXT (1.0 Кб, 67 просмотров)
0
Эксперт С++
4725 / 2546 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
04.04.2012, 20:55 4
Цитата Сообщение от adeoo Посмотреть сообщение
но программа, которую вы написали, накрылась на тестах
была опечатка. проверяйте:
Pascal
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
var 
a: array[1..100,1..4] of integer; 
num, time, res: array[1..100] of integer;
mas_kontr: array[1..100] of boolean;
n, d, v, r, i, min, t: integer;
begin
 assign(input, 'input.txt'); reset(input);
  assign(output, 'output.txt'); rewrite(output);
read(n,d,v,r);
for i:=1 to r do
read(a[i][1], a[i][2], a[i][3], a[i][4]);
for i:=1 to n do
time[i]:=2000000;
time[d]:=0;
while true do
begin
min:=0;
for i:=1 to n do
if (mas_kontr[i]=false) and (time[i]<>2000000) then
begin
if min=0 then min:=i
else
  if time[i]<time[min] then min:=i;
end;
if min=0 then break;
for i:=1 to r do
if a[i][1]=min then
begin
  if (mas_kontr[a[i][3]]=false) and (a[i][2]>=time[min]) and (time[a[i][3]]>a[i][4]) then
  begin 
  time[a[i][3]]:=a[i][4];
  num[a[i][3]]:=min;
  end;  
end;
mas_kontr[min]:=true;
end;
if time[v]=2000000 then writeln(-1)
else
begin
writeln(time[v]);
t:=v;
n:=1;
while(t>0) do
begin
res[n]:=t;
t:=num[t];
inc(n);
end;
for i:=n-1 downto 1 do
write(res[i],' ');
writeln;
end;
end.
1
0 / 0 / 0
Регистрация: 03.04.2012
Сообщений: 4
04.04.2012, 21:20  [ТС] 5
valeriikozlov, Спасибо огромное=) Программа работает правильно=)
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
04.04.2012, 21:20
Помогаю со студенческими работами здесь

Найти кратчайший маршрут
Пожалуйста, помогите!!! Имеется несколько городов, связанных в виде графа. Каждое ребро графа...

Кратчайший маршрут робота
Нужно написать программу для определения маршрута робота.В клеточном поле двигается робот. Имеется...

Найти кратчайший маршрут
Пожалуйста, помогите!!! Имеется несколько городов, связанных в виде графа. Каждое ребро графа...

Найти кратчайшее расстояние между двумя вершинами в графе. Найти все возможные пути между этими двумя вершинам
Найти кратчайшее расстояние между двумя вершинами в графе. Найти все возможные пути между этими...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru