-
Notifications
You must be signed in to change notification settings - Fork 0
/
Shortest path.cpp
77 lines (70 loc) · 1.28 KB
/
Shortest path.cpp
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
/*
problem: shortest path find
Algorithm: BFS
input:
8 9
0 1
0 3
1 2
3 4
3 7
4 5
4 6
5 6
6 7
2 6
output:
distance: 5
shortest path: 2 1 0 3 4 6
*/
#include <bits/stdc++.h>
using namespace std;
const int mx = 1e4+9;
vector<int> adj[mx];
bool visit[mx];
vector<int> parent;
int dis[mx];
int node, edge, source, dest;
vector<int> path;
int bfs() {
parent.assign(node,-1);
queue<int> q;
q.push(source);
visit[source] = true;
dis[source] = 0;
while ( !q.empty()){
int u = q.front();
q.pop();
for (auto v:adj[u]){
if (!visit[v]) {
q.push(v);
dis[v] = dis[u]+1;
visit[v] = true;
parent[v] = u;
}
}
}
cout << "distance: " << dis[dest] << endl;
path.push_back(dest);
while( parent[dest]!=-1 ) {
path.push_back(parent[dest]);
dest = parent[dest];
}
cout << "shortest path: ";
for (int i = path.size()-1; i>=0; i--) {
cout << path[i] << " ";
}
}
int main() {
//freopen( "in.txt", "r", stdin );
cin >> node >> edge;
for (int i = 0; i<edge; i++ ) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
cin >> source >> dest;
bfs();
return 0;
}