백준 1238 파티 c++ // 다익스트라 여러정점 돌리기

https://www.acmicpc.net/problem/1238

1238번: 파티

1. 시간복잡도

다익스트라 : EleE * N(학생마다 다익스트라) * 2(끝~시작지점도 반복)

10000 lg10000 * 1000 *2 <1억 -> 가능

 

2.전체코드

st와 en을 수정하면서 학생마다 다익을 돌린다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m, x, st, en,ret;
vector<pair<int, int>> adj[1004];	//adj[1]:{2,3} 1->2로가는비용이 3임
int d[1004], pre[1004]; //시작~해당정점까지 최단거리
int INF = 987654321;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);


	cin >> n >> m>>x;
	while (m--) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({ w,v });
	}

	for (int i = 1; i <= n; ++i) {
		int sum = 0;
		//1. 집~en 가기
		fill(d, d + 1004, INF);
		st = i;
		en = x;
		//{비용, 대상정점}
		priority_queue<pair<int, int>,
			vector<pair<int, int>>,
			greater<pair<int, int>>> pq;
		d[st] = 0;
		pq.push({ d[st],st });
		while (pq.size()) {
			auto cur = pq.top(); pq.pop();
			//2. 해당 거리가 최단거리테이블값과 다르면
			//더짧은경로가 있음 -> 무쓸모 -> pass
			if (d[cur.second] != cur.first) continue;
			//3. 이웃한 정점들에대해 직진보다 현재정점을 거치는게 더 싸면 
			//d갱신, 큐에추가
			for (auto next : adj[cur.second]) {
				if (d[next.second] > d[cur.second] + next.first) {
					d[next.second] = d[cur.second] + next.first;
					pq.push({ d[next.second] ,next.second });
					pre[next.second] = cur.second;
					//경로복원 : (이전정점을 기록만하면된다)
					//pre[next.정점]=cur.정점 
				}
			}
		}
		sum += d[en];

		//1. 집~en 가기
		fill(d, d + 1004, INF);
		st = x;
		en = i;
		//{비용, 대상정점}
		priority_queue<pair<int, int>,
			vector<pair<int, int>>,
			greater<pair<int, int>>> pq2;
		d[st] = 0;
		pq2.push({ d[st],st });
		while (pq2.size()) {
			auto cur = pq2.top(); pq2.pop();
			//2. 해당 거리가 최단거리테이블값과 다르면
			//더짧은경로가 있음 -> 무쓸모 -> pass
			if (d[cur.second] != cur.first) continue;
			//3. 이웃한 정점들에대해 직진보다 현재정점을 거치는게 더 싸면 
			//d갱신, 큐에추가
			for (auto next : adj[cur.second]) {
				if (d[next.second] > d[cur.second] + next.first) {
					d[next.second] = d[cur.second] + next.first;
					pq2.push({ d[next.second] ,next.second });
					pre[next.second] = cur.second;
					//경로복원 : (이전정점을 기록만하면된다)
					//pre[next.정점]=cur.정점 
				}
			}
		}
		sum += d[en];
		//2.en~집 돌아오기
		ret = max(ret, sum);
	}
	cout << ret;

	return 0;
}

 

3.리팩토링

1. 다익스트라함수(st,en)를 만들고 매개변수로 반복문 돌리는게 깔끔하다.

// Authored by : scsc3204
// Co-authored by : -
// http://boj.kr/0e6ad8751a9748d7bd32b9115678b6f6
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int n, m;
vector<pair<int,int>> adj[1002];

int solve(int st, int en){
  int d[1002];
  fill(d, d + n + 1, INF);
  priority_queue< pair<int,int>,
                  vector<pair<int,int>>,
                  greater<pair<int,int>> > pq;
  d[st] = 0;
  pq.push({0, st});
  while(!pq.empty()){
    int u, v, w, dw;
    tie(w, u) = pq.top(); pq.pop();
    if(d[u] != w) continue;
    for(auto nxt : adj[u]){
      tie(dw, v) = nxt;
      if(dw + w < d[v]) {
        d[v] = dw + w;
        pq.push({d[v], v});
      }
    }
  }
  return d[en];
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);

  int en;
  cin >> n >> m >> en;

  int u, v, w;
  while(m--) {
    cin >> u >> v >> w;
    adj[u].push_back({w, v});
  }

  int ans = 0;
  for(int st = 1; st <= n; st++)
    ans = max(ans, solve(st, en) + solve(en, st));
  cout << ans;
}