[training day3] reconstruction of roads [SPFA]

Ideas ：

Run straight spfa That's it

$code$

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>

using namespace std;

const int MAXN = 105;

int n, m, d;
int ma[MAXN][MAXN], dis[MAXN];
bool v[MAXN], f[MAXN][MAXN];
int head[MAXN], tot;

queue<int> q;

bool Floyd() {
    
	for(int k = 1; k <= n; k ++)
		for(int i = 1; i <= n; i ++)
			for(int j = 1; j <= n; j ++)
				f[i][j] = (f[i][j] | (f[i][k] & f[k][j]));
}

int main() {
    
	freopen("road.in", "r", stdin);
	freopen("road.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i ++) {
    
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		ma[x][y] = ma[y][x] = z;
		f[x][y] = f[y][x] = 1;
	}
	scanf("%d", &d);
	for(int i = 1; i <= d; i ++) {
    
		int x, y;
		scanf("%d%d", &x, &y);
		f[x][y] = f[y][x] = 0;
	}
	Floyd();
	int A, B;
	scanf("%d%d", &A, &B);
	memset(dis, 0x3f, sizeof(dis));
	v[A] = 1, dis[A] = 0, q.push(A);
	while(!q.empty()) {
    
		int x = q.front();
		q.pop();
		for(int i = 1; i <= n; i ++) {
    
			int w = 0;
			if(f[x][i] == 1) w = 0;
			else if(ma[x][i] != 0) w = ma[x][i];
			else w = dis[0];
			if(dis[x] + w < dis[i]) {
    
				dis[i] = dis[x] + w;
				if(v[i] == 0) {
    
					v[i] = 1;
					q.push(i);
				}
			}
		}
		v[x] = 0;
	}
	printf("%d", dis[B]);
	return 0;
}