-
Notifications
You must be signed in to change notification settings - Fork 0
/
Week11Exercise1(SPFA).cpp
65 lines (65 loc) · 1.8 KB
/
Week11Exercise1(SPFA).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
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <unordered_map>
using namespace std;
unordered_map<string, long> dict;
struct edge { long u, v, w; }e[150];
char place[50][30], p1[30], p2[30];
long firstEdge[50], nextEdge[150];
long matrix[50][50];
long P, Q, R, s, t, weight, tot;
inline void addEdge(long u, long v, long w) {
++tot, e[tot].u = u, e[tot].v = v, e[tot].w = w;
nextEdge[tot] = firstEdge[e[tot].u], firstEdge[e[tot].u] = tot;
}
inline void shortestPath(long s, long t) {
long dis[50], path[50], inq[50];
queue<long> q;
memset(dis, 1, sizeof(dis));
memset(path, 1, sizeof(path));
memset(inq, 0, sizeof(inq));
dis[s] = path[s] = 0, inq[s] = 1;
q.push(s);
while (!q.empty()) {
long x = q.front();
q.pop(), inq[x] = 0;
for (long i = firstEdge[x]; i != -1; i = nextEdge[i]) {
if (dis[e[i].v] > dis[e[i].u] + e[i].w) {
dis[e[i].v] = dis[e[i].u] + e[i].w, path[e[i].v] = e[i].u;
if (!inq[e[i].v]) inq[e[i].v] = 1, q.push(e[i].v);
}
}
}
stack<long> st;
long x = t;
while (path[x]) st.push(x), x = path[x];
printf("%s", place[s]);
x = s;
while (!st.empty()) {
printf("->(%ld)->%s", matrix[x][st.top()], place[st.top()]);
x = st.top(), st.pop();
}
printf("\n");
}
int main() {
scanf("%ld", &P);
for (long i = 1; i <= P; i++) {
scanf("%s", place[i]), dict[string(place[i])] = i;
}
scanf("%ld", &Q);
memset(firstEdge, -1, sizeof(firstEdge));
memset(matrix, 1, sizeof(matrix));
for (long i = 1; i <= Q; i++) {
scanf("%s%s%ld", p1, p2, &weight);
s = dict[string(p1)], t = dict[string(p2)];
if (matrix[s][t] > weight) matrix[s][t] = matrix[t][s] = weight;
addEdge(s, t, weight), addEdge(t, s, weight);
}
scanf("%ld", &R);
for (long i = 1; i <= R; i++) {
scanf("%s%s", p1, p2), s = dict[string(p1)], t = dict[string(p2)];
shortestPath(s, t);
}
}