ll d[100][100];
int main(){
ll N, M;
cin >> N >> M;
rep(i, N){
rep(j, N){
if(i!=j) d[i][j] = inf;
}
}
rep(i, M){
ll a, b, c;
cin >> a >> b >> c;
a--; b--;
d[a][b] = c;
d[b][a] = c;
}
rep(i, N){
rep(j, N){
rep(k, N){
d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
}
}
}
}
目的
- コピー用
- 行列初期化を忘れるというミスをした。それを今後は防ぐため
verified
- D - Candidates of No Shortest Paths
クラス化
struct WarshallFloyd{
VV d;
ll N;
bool pre_calculated = false;
WarshallFloyd(ll n){
if(n>=2000){
cerr << "[warning]maybe data size is too big";
}
N = n;
d.resize(N, VI(N, inf));
rep(i, N) d[i][i] = 0;
}
void register_edge(ll a, ll b, ll c){
d[a][b] = c;
}
void register_edge2(ll a, ll b, ll c){
register_edge(a,b,c);
register_edge(b,a,c);
}
void calc(){
rep(i, N){
rep(j, N){
rep(k, N){
d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
}
}
}
pre_calculated = true;
}
ll distance(ll a, ll b){
if(!pre_calculated){
debug("auto calc");
calc();
}
return d[a][b];
}
};
verified