FilesExpand file tree

 master

/

number_of_shortest.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

75 lines (55 loc) · 1.35 KB

 master

/

number_of_shortest.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

75 lines (55 loc) · 1.35 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

const int MAXN = 100;

typedef pair<int, int> pii;

vector< int> G[MAXN];

bool visited[MAXN];

int cnt[MAXN];

void work(){

queue< pii > Q;

Q.push( pii(0, 1) );

memset(cnt, 0, sizeof(cnt));

visited[0] = 1;

while(1){

queue< pii > _tmp;

vector<int> mark;

while(!Q.empty()){

pii cur = Q.front();Q.pop();

for(int i=0; i<G[cur.first].size(); i++){

int next = G[cur.first][i];

int v = cur.second;

if(visited[next]==0){

_tmp.push( pii(next, v) );

cnt[next] += v;

mark.push_back(next);

}

}

}

for(int i=0; i<mark.size(); i++){

visited[mark[i]] = 1;

}

if(_tmp.size() == 0)break;

Q = _tmp;

cout<<"-------------"<<endl;

for(int i=0; i<=7; i++){

cout<<i<<" "<<cnt[i]<<endl;

}

}

}

int main(){

G[0].push_back(1);

G[0].push_back(2);

G[0].push_back(3);

G[1].push_back(2);

G[1].push_back(5);

G[2].push_back(4);

G[3].push_back(4);

G[4].push_back(5);

G[4].push_back(6);

G[5].push_back(6);

G[6].push_back(7);

work();

return 0;

}