• 박인서
• 15이원준

# 3. 코드 ¶

## 3.1. 15이원준 ¶

```#include<iostream>
using namespace std;

int arr[1002][1002], dist[1002], go[1002];
bool sp[1002];
int N, M, X;
void dijks(int start){
for(int i = 1; i<= N; i++){
sp[i] = false;
dist[i] = -1;
if(i == start){
dist[i] = 0;
}
}
int now = start;
sp[now] = true;
dist[now] = 0;
for(int k = 1; k< N; k++ ){
for(int i = 1; i<= N; i++){
if(arr[now][i] == -1 || sp[i] == true){

}
else if(dist[i] == -1 || dist[i] > dist[now] + arr[now][i]){
dist[i] = dist[now] + arr[now][i];
//cout<< i << " " << dist[i] << " " << dist[now] << " " << arr[now][i]<< endl;
}
//cout<< now << " "<< i << " " << dist[i]<< " " << arr[now][i]<< endl;
}
int min = -1;
for(int i = 1; i<= N; i++){
if(sp[i] == false && dist[i] != -1 && (min == -1 || dist[min] > dist[i]))
min = i;
}
now = min;
sp[now] = true;
}
/*for(int i = 1; i<= N; i++){
cout<<i <<" " <<dist[i] << endl;
}*/
}
void gototown(int start){
for(int i = 1; i<= N; i++){
sp[i] = false;
go[i] = -1;
if(i == start){
go[i] = 0;
}
}
int now = start;
sp[now] = true;
go[now] = 0;
for(int k = 1; k< N; k++ ){
for(int i = 1; i<= N; i++){
if(arr[i][now] == -1 || sp[i] == true){

}
else if(go[i] == -1 || go[i] > go[now] + arr[i][now]){
go[i] = go[now] + arr[i][now];
//cout<< i << " " << dist[i] << " " << dist[now] << " " << arr[now][i]<< endl;
}
//cout<< now << " "<< i << " " << dist[i]<< " " << arr[now][i]<< endl;
}
int min = -1;
for(int i = 1; i<= N; i++){
if(sp[i] == false && go[i] != -1 && (min == -1 || go[min] > go[i]))
min = i;
}
now = min;
sp[now] = true;
}
/*for(int i = 1; i<= N; i++){
cout<<i <<" " <<dist[i] << endl;
}*/
}
int main(){
cin>> N >> M >> X;
for(int i = 1; i<=N; i++){
for(int j = 1; j<= N; j++){
arr[i][j] = -1;
}
}
for(int i = 0; i<M; i++){
int s, e, t;
scanf("%d %d %d", &s, &e, &t);
arr[s][e] = t;
}

gototown(X);
dijks(X);
int max = 0;
for(int i = 1; i<= N; i++){
if(max < go[i] + dist[i]){
//cout << i << " " << go[i] << " " << dist[i];
max = go[i] + dist[i];
}
}
cout << max;

}
```

## 3.2. 박인서 ¶

```#include <iostream>
#define MAX_INT 217483647
using namespace std;

int edge[1001][1001], dist[2][1001];
bool visit[2][1001];

int main()
{
int n, m, s, i, j;
//입력 및 초기화
cin >> n >> m >> s;
for (i = 0; i<m; i++)
{
int a, b, c;
cin >> a >> b >> c;
edge[a][b] = c;
}
for (i = 0; i <= n; i++)
{
visit[0][i] = false, visit[1][i] = false;
dist[0][i] = MAX_INT, dist[1][i] = MAX_INT;
}
//첫번째도 두번째도 시작점에서 dist = 0
dist[0][s] = 0, dist[1][s] = 0;
for (i = 0; i<n; i++)
{
int min1 = 0, min2 = 0;
//min1,min2값 탐색
for (j = 1; j <= n; j++)
{
if (visit[0][j] == false && dist[0][min1]>dist[0][j]) min1 = j;
if (visit[1][j] == false && dist[1][min2]>dist[1][j]) min2 = j;
}
//visit check
visit[0][min1] = true;
visit[1][min2] = true;
//경로 탐색
for (j = 1; j <= n; j++)
{
//기존 dijkstra와 동일
if (dist[0][j]>dist[0][min1] + edge[min1][j] && edge[min1][j] != 0) dist[0][j] = dist[0][min1] + edge[min1][j];
//반대로 edge를 먼저 생각하고 dist를 생각한다.
if (dist[1][j]>edge[j][min2] + dist[1][min2] && edge[j][min2] != 0) dist[1][j] = edge[j][min2] + dist[1][min2];
}
}
//최댓값 탐색
int res = 0;
for (i = 1; i <= n; i++)
{
if (res<dist[0][i] + dist[1][i] && dist[0][i] != MAX_INT && dist[1][i] != MAX_INT) res = dist[0][i] + dist[1][i];
}
//출력
cout << res;
return 0;
}
```

# 4. 아이디어 ¶

## 4.1. 15이원준 ¶

• 올때는 도착지에서 출발하는 다익스트라를 이용하였습니다.
• 도중에 가는 것도 구해야 한다는 것을 알게 되었고 처음에 각 출발지를 기준으로 다익스트라를 N번했으나 시간초과가 났습니다.
• 잘 생각해보니 arr(각 다리사이의 시간)의 i,j를 바꾸고 도착지에서 출발하면 똑같은 결과를 얻을 수 있다는 생각을 했습니다.

## 4.2. 박인서 ¶

• 파티에 참석하러 갈 때는 그냥 dijkstra 알고리즘을 이용하면 됨.
• 문제는 참석하고 돌아올 때인데 이 때는 그냥 출발지와 도착지를 반대로 바꾸어 생각해주면 된다.