on
프로그래머스 합승 택시 요금 CPP/C++/python
프로그래머스 합승 택시 요금 CPP/C++/python
#include < string >
#include < vector >
using namespace std ;
int INF;
int min( int a, int b){
return a < b ? a : b;
}
int solution( int n, int s, int a, int b, vector < vector < int > > fares) {
int answer = 0 ;
int board[n][n];
int i, j, k;
INF = n * 100000 ;
for (i = 0 ; i < n;i + + ){
for (j = 0 ;j < n;j + + )
board[i][j] = INF;
}
vector < vector < int > > :: iterator it;
for (it = fares. begin (); it ! = fares. end (); it + + ){
board[( * it)[ 0 ] - 1 ][( * it)[ 1 ] - 1 ] = ( * it)[ 2 ];
board[( * it)[ 1 ] - 1 ][( * it)[ 0 ] - 1 ] = ( * it)[ 2 ];
}
for (i = 0 ;i < n;i + + ){ // pass
for (j = 0 ;j < n;j + + ){ // src
for (k = 0 ;k < n;k + + ){ // des
if (j = = k | | i = = j | | i = = k) continue ;
board[j][k] = min(board[j][k], board[j][i] + board[i][k]);
}
}
}
answer = board[s - 1 ][a - 1 ] + board[s - 1 ][b - 1 ];
for (i = 0 ;i < n;i + + ){
if (board[s - 1 ][i] = = INF) continue ;
if (i = = a - 1 )
answer = min(answer, board[s - 1 ][i] + board[i][b - 1 ]);
else if (i = = b - 1 )
answer = min(answer, board[s - 1 ][i] + board[i][a - 1 ]);
else
answer = min(answer, board[s - 1 ][i] + board[i][a - 1 ] + board[i][b - 1 ]);
}
return answer;
}
from http://nooblette.tistory.com/225 by ccl(A) rewrite - 2021-09-09 18:26:48