1307-D, *1900

Problem - D - Codeforces

 

 

풀이

Xa+Yb 가 가장 클 때를 찾아야하는 이유는 Xa+Yb+1 이 노드 1부터 n 까지 (노트 a, b를 경유하는) 최단거리이기 때문

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
#define all(v) (v).begin(), (v).end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
 
const int INF = 1e6;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int n, m, k; cin >> n >> m >> k;
    vector<int> special(k);
    for(auto& e: special) cin >> e;
    map<int, vector<int> > edge;
 
    loop(i, m){
        int u, v; cin >> u >> v;
        edge[u].emplace_back(v);
        edge[v].emplace_back(u);
    }
 
    vector<int> cnt_from_1(n+1, INF);
    queue<int> q;
    q.push(1);
    cnt_from_1[1] = 0;
    while(!q.empty()){
        auto cur = q.front(); q.pop();
        int nex_cnt = cnt_from_1[cur] + 1;
        for(const auto nex: edge[cur]){
            if(nex_cnt < cnt_from_1[nex]){
                if(nex != n) q.push(nex);
                cnt_from_1[nex] = nex_cnt;
            }
        }
    }
 
    vector<int> cnt_from_n(n+1, INF);
    q.push(n);
    cnt_from_n[n] = 0;
    while(!q.empty()){
        auto cur = q.front(); q.pop();
        int nex_cnt = cnt_from_n[cur] + 1;
        for(const auto nex: edge[cur]){
            if(nex_cnt < cnt_from_n[nex]){
                if(nex != 1) q.push(nex);
                cnt_from_n[nex] = nex_cnt;
            }
        }
    }
 
    vector<pi> tmp;
    ooop(i, k) tmp.emplace_back(cnt_from_1[special[i]]-cnt_from_n[special[i]], special[i]);
    sort(all(tmp));
    int maxval = 0, max_ind;
    ooop(i, k-1){
        int a = tmp[i].second, b = tmp[i+1].second;
        int dis = cnt_from_1[a] + cnt_from_n[b];
        if(maxval < dis){
            maxval = dis;
            max_ind = i;
        }
    }
 
    cout << min(cnt_from_1[n], maxval+1) << endl;
 
    return 0;
}cs