백준 17270 연예인은 힘들어

https://www.acmicpc.net/problem/17270

간단한 그래프 문제입니다. 노드의 개수가 100이하로 충분히 작기 때문에 벨만 포드 알고리즘, 다익스트라 알고리즘 등등 어떤 방법으로 풀어도 풀립니다.

저는 벨만포드 방정식으로 dist[a][b]에 a에서 b로 가는 최단 거리를 저장하여 풀었습니다.

#include<bits/stdc++.h>
using namespace std;
const int SZ=105;
int memo[SZ][SZ];
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	int n,m; cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) if(i!=j) memo[i][j]=INT_MAX;
	}
	for(int i=0;i<m;i++){
		int a,b,c; cin>>a>>b>>c;
		memo[a][b]=min(memo[a][b],c);
		memo[b][a]=memo[a][b];
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			if(i==k) continue;
			for(int j=1;j<=n;j++){
				if(i==j || j==k) continue;
				if(memo[i][k]!=INT_MAX && memo[k][j]!=INT_MAX){
					memo[i][j]=min(memo[i][j],memo[i][k]+memo[k][j]);
					memo[j][i]=memo[i][j];
				}
			}
		}
	}
	int s,e; cin>>s>>e;
	int ans=-1, dist=INT_MAX;
	if(memo[s][e]==INT_MAX){
		cout<<ans;
		return 0;
	}
	int mnd=INT_MAX;
	for(int i=1;i<=n;i++){
		if(i==s || i==e) continue;
		if(memo[s][i]==INT_MAX || memo[e][i]==INT_MAX) continue;
		mnd=min(mnd,memo[s][i]+memo[e][i]);
	}
	for(int i=1;i<=n;i++){
		if(i==s || i==e) continue;
		if(memo[s][i]==INT_MAX || memo[e][i]==INT_MAX) continue;
		if(mnd!=memo[s][i]+memo[e][i]) continue;
		if(memo[s][i]>memo[e][i]) continue;
		if(dist>memo[s][i]){
			ans=i;
			dist=memo[s][i];
		}
	}
	cout<<ans;
	return 0;
}