code container dijkstra

aza (3)
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
 
#include<queue>
#include<iostream>
#include<math.h>
using namespace std;

#define MAXINT 1000000
#define MAX 1000  


int graf[MAX][MAX];
int wierzcholki;             
                 

int waga[MAX];          
int poprzednik[MAX];     
bool odwiedzone[MAX]; 

void dijkstra(int start)
{
  priority_queue<pair<int,int> > kolejka;
  pair <int,int> obecny_wierzcholek;
  int i, j;
  
  for (int i=1; i<=wierzcholki; i++) {
    waga[i] = MAXINT;
    poprzednik[i] = -1;
    odwiedzone[i] = false;
  }
 
  waga[start] = 0;
  kolejka.push(pair <int,int> (waga[start], start));
 
  while(!kolejka.empty()) {
    obecny_wierzcholek = kolejka.top();  
    kolejka.pop();
    i = obecny_wierzcholek.second;
    if (!odwiedzone[i]) {
      odwiedzone[i] = true;
      for (j = 1; j<=wierzcholki; j++)
        if (!odwiedzone[j] && graf[i][j] > 0 && waga[i] + graf[i][j] < waga[j]) {
          waga[j] = waga[i] + graf[i][j];
          poprzednik[j] = i;
          kolejka.push(pair <int,int>(-waga[j], j));
        }
    }
  }
}


void sciezka(int koniec) {
     int waga_drogi=0;
   cout << koniec << " ";
  while (poprzednik[koniec]!= -1) {
      waga_drogi+=graf[poprzednik[koniec]][koniec]; 
   cout << poprzednik[koniec] << " ";
    koniec = poprzednik[koniec];
  }
  printf("%d\n", waga_drogi);
}

int main()
{
   int a, b, c,d,t,start,koniec;
   int krawedzie;
 
   scanf("%d", &t);
	   for(int i=0;i<t;i++)
	   {
   memset(graf, 0, sizeof(graf));
   scanf("%d %d %d %d", &wierzcholki, &krawedzie, &start, &koniec); 
   
   for (int i=0; i<krawedzie; i++) {
     scanf("%d %d %d %d", &a, &b, &c, &d);
	
     graf[a][b] = c;
	 if(d==2)graf[b][a]=c;
   }
   for(int i=1; i<=wierzcholki; i++) {
      for(int j=1; j<=wierzcholki; j++)
         printf("%d ", graf[i][j]);
      printf("\n");
   }
   dijkstra(start);
   sciezka(koniec);
	   }

   return 0;
}
Return 0 (1282)
Is there a question here or are you storing code for your final exam?
coder777 (8450)
hmm, maybe it's guessing game. What's the language used there (besides c++)?
Seraphimsan (954)
i think its c
coder777 (8450)
ok, the language besides the programming language
chrisname (7395)
Well, Dijkstra was Dutch but that doesn't look like Dutch. It looks like a Slavic language of some kind, maybe Polish or Serbian.
hamsterman (4538)
google detects polish.
aza (3)
Exactly Polish language,
;-)
aza (3)
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
 

#include <stdio.h>

#include <stdlib.h>

#define niesk 1000000000

int *N, np;
long long int *D;

int najmniejszy();

void Dijkstra(int, int);

int m, n,start,koniec;
//wierzchołki n ## krawędzie m 
struct S_kraw
{
int gdzie;
int waga;
};
struct S_wierz
{
int ile_kraw;
struct S_kraw *kraw;
void dodaj_kraw(int,int);
void zwolnij_pamiec();
};
struct S_wierz *wierz;
void S_wierz::dodaj_kraw(int dest,int length)
{
this->ile_kraw++;
this->kraw = (struct S_kraw *) realloc(this->kraw,((sizeof(struct S_kraw))*(this->ile_kraw)));
this->kraw[this->ile_kraw-1].gdzie = dest;
this->kraw[this->ile_kraw-1].waga = length;
}
void S_wierz::zwolnij_pamiec()
{
free(this->kraw);
this->kraw = NULL;
}
int main()
{
int zestawy;
scanf("%d" , &zestawy);
for(int i=0;i<zestawy;i++)
{
scanf("%d",&n);
scanf("%d",&m);
scanf("%d",&start);
scanf("%d",&koniec);

wierz = new struct S_wierz[n];
for(int i=0; i<n ;i++)
{
wierz[i].ile_kraw = 0;
wierz[i].kraw = NULL;
}
int a, b, c, dw;
for(int i=0; i<m; i++)
{
scanf("%d",&a);
scanf("%d",&b);
scanf("%d",&c);
scanf("%d",&dw);
if(m==1){printf("%d\n",c);goto jedna;}
wierz[(a-1)].dodaj_kraw((b-1),c);
if (dw==2) wierz[(b-1)].dodaj_kraw((a-1),c);
}
Dijkstra(start-1, n);
printf("%d\n",D[koniec-1]);
delete[] D,N;
jedna:{}
}
return 0;
}


// s szukamy drogi od wirzchołka  wirzchołka(tablica od 0), n ilość wierzchołków 
void Dijkstra(int s, int n)
{
  np = 0;
  D = new long long int[n];
  N = new int[n];
for(int i=0; i<n; i++)
   D[i] = niesk;
      
      for(int i=0; i<wierz[s].ile_kraw; i++)
      D[wierz[s].kraw[i].gdzie] = wierz[s].kraw[i].waga;
  
  D[s] = 0;
      for(int i=0; i<n; i++)
      {
        if(i==s)
        continue;
        N[np++] = i;
}
while(np>0)
{
int i = najmniejszy();
for(int k=0; k<wierz[i].ile_kraw; k++)
if(D[wierz[i].kraw[k].gdzie] > D[i]+wierz[i].kraw[k].waga)
D[wierz[i].kraw[k].gdzie] = D[i]+wierz[i].kraw[k].waga;
}
}
int najmniejszy()
{
int val, num, result;
val = niesk;
for(int i=0; i<np; i++)
{
if(D[N[i]] < val)
{
val = D[N[i]];
num = i;
}
}
result = N[num];
np--;
N[num] = N[np];
return result;
}
Topic archived. No new replies allowed.