#include<iostream> #include<bits/stdc++.h> #define LOCAL #define int long long #define MAXN 10020 #define INF 0x3f3f3f usingnamespacestd; int t, n, m; vector<int> edge[MAXN]; //邊的陣列 int visit[MAXN]; int dist[MAXN], important[MAXN]; //dist 從 x 到 index 的距離 //important 重要車站,當經過的路徑大於 2,就是重要車站
//不使用 dijkstra,因為每一個權重都相同,因此使用普通的 queue 就好 intspfa(int root){ //don't using dijkstra, because each have same weights for(int i = 1; i <= n; i++) dist[i] = INF; //root 一開始無法抵達這些點,因此都次 INF memset(visit, 0, sizeof(visit));
int ans = 0; for(int i = 1; i <= n; i++){ //計算可以抵達每一個車站,使用多少距離 if(important[i] > 1) ans += dist[i]; //如果 root 沒辦法抵達此車站,那就會是 +INF } return ans; }
int32_tmain() { #ifdef LOCAL freopen("in1.txt", "r", stdin); #endif// LOCAL cin >> t; while(t--){ cin >> n >> m; for(int i = 1; i <= n; i++) edge[i].clear();