acmicpc.net 11404(플로이드), 11403(플로이드), 1389(플로이드)

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

플로이드.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
  
int n,m,v,a,b,c;
int adj[101][101];
int w[101][101];

void floyd()
{
	for(int k=1;k<n+1;k++)
		for(int i=1;i<n+1;i++)
			for(int j=1;j<n+1;j++)
				if(w[i][j] > w[i][k]+w[k][j])
					w[i][j] = w[i][k]+w[k][j];
}

     
int main()
{
    ios::sync_with_stdio(false); 
    cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		cin>>a>>b>>c;
		if(w[a][b]==0)
			w[a][b] = c;
		else
			w[a][b] = min(w[a][b], c);
	}
	floyd();
	for(int i=1;i<n+1;i++)
	{
		for(int j=1;j<n+1;j++)
			cout<<w[i][j]<<" ";
		cout<<'\n';
	}
    return 0;
}

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

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
  
int n,m,v,a,b,c;
long long w[101][101];
long long INF = 99999999999;

void floyd()
{
	for(int k=1;k<n+1;k++)
		for(int i=1;i<n+1;i++)
			for(int j=1;j<n+1;j++)
				if(w[i][j] > w[i][k]+w[k][j])
					w[i][j] = w[i][k]+w[k][j];
}

     
int main()
{
    ios::sync_with_stdio(false); 
    cin>>n;
	for(int i=1;i<n+1;i++)
		for(int j=1;j<n+1;j++)
		{
			cin>>c;
			w[i][j] = c;
			if(c==0) 
				w[i][j]=INF;
		}
	floyd();
	for(int i=1;i<n+1;i++)
	{
		for(int j=1;j<n+1;j++)
		{
			if(w[i][j]!=INF)
				cout<<1<<" ";
			else
				cout<<0<<" ";
		}
		cout<<'\n';
	}
    return 0;
}

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

별거 없다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
  
int n,m,v,a,b,c;
long long w[101][101];
long long INF = 99999999999;

void floyd()
{
	for(int k=1;k<n+1;k++)
		for(int i=1;i<n+1;i++)
			for(int j=1;j<n+1;j++)
				if(w[i][j] > w[i][k]+w[k][j])
					w[i][j] = w[i][k]+w[k][j];
}

     
int main()
{
    ios::sync_with_stdio(false); 
    cin>>n>>m;
	for(int i=1;i<n+1;i++)
		for(int j=1;j<n+1;j++)
			w[i][j] = INF;

	for(int i=0;i<m;i++)
	{
		cin>>a>>b;
		w[a][b] = 1;
		w[b][a] = 1;
	}

	floyd();
	int min = INF, person = INF;
	for(int i=1;i<n+1;i++)
	{
		int submin = 0;
		for(int j=1;j<n+1;j++)
		{
			if(i==j) continue;
			submin += w[i][j];
		}
		if(min > submin)
		{
			min = submin;
			person = i;
		}
	}
	cout<<person<<'\n';
    return 0;
}