백준 1956 운동 C++

 

 

간단한 해설

 

v가 적고, 간선 또한 v*(v-1)개이다에서 사실 플로이드를 염두에 두고 있었으나, 다익스트라로 풀리나 한번 해봤다.

 

결국 33~36%대에서 시간초과가 나서 플로이드로 풀었다.

 

 

플로이드를 구현하는 법은 상당히 간단하다.

 

for문을 3번 돌리는데 이런 식으로 생각하면 편하다.

 

for(int k=1;k<=v;++k){ // 거쳐가는 정점
    for(int i=1;i<=v;++i){ // 출발 정점
        for(int j=1;j<=v;++j){ // 도착 정점
            if(graph[i][k]==987654321||graph[k][j]==987654321) continue; // 쓰레기값 여과
            graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j]);
        }
    }

 

답

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> graph; 
int ans=987654321;
int v,e;
int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cin>>v>>e;
	graph.resize(v+1,vector<int>(v+1,987654321));
	int a,b,c;
	for(int i=0;i<e;++i){
		cin>>a>>b>>c;
		graph[a][b]=c;
	}
	for(int k=1;k<=v;++k){
		for(int i=1;i<=v;++i){
			for(int j=1;j<=v;++j){
				if(graph[i][k]==987654321||graph[k][j]==987654321) continue;
				graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j]);
			}
		}
	}
	for(int i=1;i<=v;++i){
		ans=min(graph[i][i],ans);
	}
	if(ans==987654321) ans=-1;
	cout<<ans;
}