题目(材料题)
给定一张有$n$个顶点、$m$条边的无向图，每条边带有符号'+'或'-'。对于一条从顶点$s$到顶点$t$的路线，允许重复经过顶点和
边，定义一条路线的权值如下:记$n^+,n^-$分别为经过的'+'边数和经过的'-'边数，则该路线的权值为$|n^+-n^-|$。
请计算从$s$到$t$的路线的最小权值。若不存在从s到t的路线，则输出-1。
输入第一行为四个整数$n,m,s,t$。接下来$m$行，每行给出两个整数$a,b$和一个字符'+或'-'，描述一条连接$a$与$b$的无向边及其符号。
数据满足$2≤n≤2\times 10^5，1≤m≤4\times10^5$，$1≤s,t≤n$且$s≠t,1≤a,b≤n$，可能出现重边。
以下程序通过BFS求出最小权值。请补全程序。
01 #include <iostream>
02
03 constexpr int N = 200005;
04 constexpr int M = 400005;
05
06 int n, m, s, t;
07 int h[N], e[M << 1], ne[M << 1], w[M << 1], idx;
08 int q[N], d[N], c[N];
09
10 void add(int a, int b, int z) {
11 e[idx] = b;
12 w[idx] = z;
13 ne[idx] = h[a];
14 h[a] = idx++;
15}
16
17 int main() {
18 std::cin >> n >> m >> s >> t;
19 for (int i = 1; i <= n; i++)
20 h[i] = d[i] = c[i] = -1;
21 for (int i = 0; i < m; i++) {
22 int a, b;
23 char op[2];
24 std::cin >> a >> b >> op;
25 int z = ____①____;
26 add(a, b, z);
27 add(b, a, z);
28 }
29 int hh = 0, tt = 0;
30 int p = 0, ng = 0, ok = 1;
31 q[tt++] = s;
32 d[s] = c[s] = 0;
33 while (____②____) {
34 int x = q[hh++];
35 for (int i = h[x]; i != -1; i = ne[i]) {
36 int y = e[i];
37 if (w[i] > 0)p = 1;
39 if (w[i] < 0)ng = 1;
40 if (d[y] == -1) {
41 d[y] = ____③____;
42 c[y] = c[x] ^ 1;
43 q[tt++] = y;
44 } else if (____④____)
45 ok = 0;
46 }
47 }
48 if (d[t] == -1) {
49 std::cout << -1;
50 return;
51 }
52 if (!p || !ng) {
53 std::cout << d[t];
54 return 0;
55 }
56 if (____⑤____) std::cout << 0;
57 else std::cout << 1;
58 return 0;
59 }
||
关注我们
