1238

파티하는 학생의 집에 까지 가는 경우와 돌아오는 경우

각각에 대해서 시간을 따로 구해야 하는것이 문제의 핵심이다.

처음에는 문제를 풀 때 각 노드 사이에 걸리는 모든 시간을 다 구해야 하나 하고 생각을 하다

파티하는 학생의 집을 출발점으로 두는것과 도착점으로 두는 것 모두 동일한 경우로 판단 할 수 있어서 다익스트라 알고리즘을 두 번 돌리는 것으로 해결했다.

각각의 노드들 마다 간선을 inflow, outflow로 arrow를 표현하니 코드가 간결해졌다.

#include<iostream> #include<cstdio> #include<queue> #include<vector> using namespace std; vector<pair<int, int> > outflow[1005]; vector<pair<int, int> > inflow[1005]; int in_d[1005]; int out_d[1005]; void dijkstra(int X, vector<pair<int, int> > adj[1005], int* d){ priority_queue<pair<int, int> >q; d[X]=0; q.push(make_pair(0, X)); //inflow while(!q.empty()){ pair<int, int> front=q.top(); q.pop(); int pos = front.second; int cost = -front.first; if(d[pos]!=-1 && d[pos] < cost) continue; for(int i=0; i<adj[pos].size(); i++){ int newpos = adj[pos][i].first; if(d[newpos]==-1){ int newcost=cost + adj[pos][i].second; d[newpos]=newcost; q.push(make_pair(-newcost, newpos)); } else{ if(d[newpos] > cost + adj[pos][i].second){ int newcost=cost + adj[pos][i].second; d[newpos]=newcost; q.push(make_pair(-newcost, newpos)); } } } } } int main(){ int N, M, X; int from, to, cost; int res=0; scanf("%d %d %d", &N, &M, &X); for(int i=1; i<=N; i++){ in_d[i]=-1; out_d[i]=-1; } for(int clk=0; clk<M; clk++){ scanf("%d %d %d", &from, &to, &cost); outflow[from].push_back(make_pair(to, cost)); inflow[to].push_back(make_pair(from, cost)); } dijkstra(X, inflow, in_d); dijkstra(X, outflow, out_d); for(int i=1; i<=N; i++) res = max(res, in_d[i]+out_d[i]); printf("%d\n", res); return 0; }