1R/2016 09 13 - Revision history

Maintenance script: Repair pages found by live-compare batch 0001

2026-03-26T14:46:15Z

Repair pages found by live-compare batch 0001

175.124.46.11 at 15:54, 18 September 2016

2016-09-18T15:54:06Z

← Older revision		Revision as of 15:54, 18 September 2016
Line 169:		Line 169:
	= 아이디어 =		= 아이디어 =
	== 15이원준 ==		== 15이원준 ==
			* 올때는 도착지에서 출발하는 다익스트라를 이용하였습니다.
			* 도중에 가는 것도 구해야 한다는 것을 알게 되었고 처음에 각 출발지를 기준으로 다익스트라를 N번했으나 시간초과가 났습니다.
			* 잘 생각해보니 arr(각 다리사이의 시간)의 i,j를 바꾸고 도착지에서 출발하면 똑같은 결과를 얻을 수 있다는 생각을 했습니다.
			* 끝
	== 박인서 ==		== 박인서 ==
	* 파티에 참석하러 갈 때는 그냥 dijkstra 알고리즘을 이용하면 됨.		* 파티에 참석하러 갈 때는 그냥 dijkstra 알고리즘을 이용하면 됨.

175.124.46.11 at 15:52, 18 September 2016

2016-09-18T15:52:14Z

← Older revision		Revision as of 15:52, 18 September 2016
Line 6:		Line 6:
	= 참가자 =		= 참가자 =
	* 박인서		* 박인서
			* 15이원준
	= 코드 =		= 코드 =
	== 15이원준 ==		== 15이원준 ==

175.124.46.11 at 15:52, 18 September 2016

2016-09-18T15:52:03Z

@@ Line 8: / Line 8: @@
 = 코드 =
 == 15이원준 ==
+ #include&lt;iostream&gt;
 == 박인서 ==
   #include &lt;iostream&gt;

1.228.80.74 at 07:22, 14 September 2016

2016-09-14T07:22:24Z

← Older revision		Revision as of 07:22, 14 September 2016
Line 72:		Line 72:

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


	== 곽정흠 ==		== 곽정흠 ==

1.228.80.74: {CREATE}

2016-09-14T07:17:05Z

{CREATE}

New page

__TOC__

= 오늘의 문제 =
* [https://www.acmicpc.net/problem/1238|파티]

= 참가자 =
* 박인서
= 코드 =
== 15이원준 ==

== 박인서 ==
#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;
}
== 곽정흠 ==

= 아이디어 =
== 15이원준 ==

== 박인서 ==

== 곽정흠 ==