백준
백준 소스코드 [C++] 1238 파티
Hani_Levenshtein
2020. 8. 26. 22:58
https://www.acmicpc.net/problem/1238
1238번: 파티
문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이
www.acmicpc.net
백준 소스코드 [C++] 1238 파티
#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
using namespace std;
int v, e, start,desti, s, d, weight,time=0;
vector <pair<int, int>> adj[1000];
vector<int> dijkstra(int src) {
priority_queue <pair<int, int> > pq;
vector<int> dist(v, INT_MAX);
dist[src] = 0;
pq.push({ 0,src });
while (pq.empty() != true) {
int cost = -pq.top().first;
int here = pq.top().second;
pq.pop();
if (dist[here] < cost) continue;
for (int i = 0;i < (int)adj[here].size();i++) {
int there = adj[here][i].first;
int nextdist = cost + adj[here][i].second;
if (dist[there] > nextdist) {
dist[there] = nextdist;
pq.push({ -nextdist,there });
}
}
}
return dist;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> v>> e >> desti;
for (int i = 0;i < e;i++) {
cin >> s >> d >> weight;
adj[s-1].push_back(make_pair(d-1, weight));
}
for(int i=1;i<=v;i++)
time=max(time,dijkstra(i-1)[desti - 1]+dijkstra(desti - 1)[i-1]);
cout << time;
return 0;
}