백준 21940 가운데에서 만나기 (C++)

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

21940번: 가운데에서 만나기

대놓고 다익스트라를 사용하라는 문제였습니다. (양의 간선 가중치)  n=200

다익스트라를 모든 점을 시작점으로 두고 돌려 다른 점에 대한 거리를 구해 배열에 저장한뒤 

마을에 대해 답을 구하는 연산을 하면 됩니다.

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<functional>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
vector<int> lcity;
vector<int> solve;
long long ans=1e18;
long long dist[201][201];
long long d[201];
vector<vector<pair<int,int>>> edge(202,vector<pair<int,int>>());
void dijkstra(int start){
    d[start]=0;
    priority_queue<pair<int,int>> pq;
    pq.push({0,start});
    while(!pq.empty()){
        int now=pq.top().second;
        int cost=-pq.top().first;
        pq.pop();
        if(d[now]<cost) continue;
        for(auto i : edge[now]){
            if(d[i.first]>cost+i.second){
                d[i.first]=cost+i.second;
                pq.push({-cost-i.second,i.first});
            }
        }
    }
}
int main(){
    fast_io();
    int N,M,K;
    cin>>N>>M;
    for(int x=0;x<M;x++){
        int src,dst,t;
        cin>>src>>dst>>t;
        edge[src].push_back({dst,t});
    }
    cin>>K;
    for(int x=0;x<K;x++){
        int input;
        cin>>input;
        lcity.push_back(input);
    }
    for(int x=1;x<=N;x++){
        for(int y=1;y<=N;y++) d[y]=1e18;
        dijkstra(x);
        for(int y=1;y<=N;y++) dist[x][y]=d[y];
    }
    for(int x=1;x<=N;x++){
        long long temp=0;
        for(auto i : lcity){
            temp=max(dist[i][x] + dist[x][i],temp);
        }
        if(ans>=temp){
            if(temp==ans){
                solve.push_back(x);
            }
            else{
                ans=temp;
                solve.clear();
                solve.push_back(x);
            }
        }
    }
    for(auto i : solve) cout<<i<<" ";
}