[[TableOfContents]] = ì˜¤ëŠ˜ì˜ ë¬¸ì œ = * [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ì´ì›ì¤€ == == ë°•ì¸ì„œ == == ê³½ì •í ==