欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Roun d #621 (Div. 1 + Div. 2) D. Cow and Fields 最短路+贪心 图上特殊点加边使最短路最大

程序员文章站 2022-06-03 18:31:39
...

题目链接:https://codeforces.ml/contest/1307/problem/D
题目大意:Codeforces Roun d #621 (Div. 1 + Div. 2) D. Cow and Fields 最短路+贪心 图上特殊点加边使最短路最大
有一个无向图n个点m条边,其中有k个特殊点。现在让你在两个特殊点之间连一条边。让1到n的最短路最大, 并且输出这个最短路的大小。

dis1[i]:1idis2[i]:niijmin(dis1[i]+dis2[j]+1,dis2[i]+dis1[j]+1)idis2[i]>=dis2[j]ijdis1[i]+dis2[j]+1dis1[n]dis1[i]+dis2[j]+1idis2[i]>=dis2[j]dis2[j]jdis2[] \begin{array}{l} dis1[i]:1到i的最短距离 \\ dis2[i]:n到i的最短距离 \\ 如果我们在i和j连边最短路可能变成:min(dis1[i]+dis2[j]+1, dis2[i]+dis1[j]+1) \\ 这里对于一个点i它和谁连并不能贪心。\\ 如果规定:dis2[i]>=dis2[j]那么i和j连边最短路只可能变成dis1[i]+dis2[j]+1。或者dis1[n]\\ 我们希望最大化:dis1[i]+dis2[j]+1。对于一个i点我们这要找到dis2[i]>=dis2[j]并且dis2[j]最大的j点。\\ 把所有特殊点的dis2[]加入容器二分就可以了。 \end{array}

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=2e5+5;

vector< pair<int ,int > > e[maxn];
vector<int> v, d;
int n, m;
int dis1[maxn], dis2[maxn];   //dis当前的最短路
int vis[maxn];   //是否已经求出最短路
priority_queue<pair<int, int> > q;
void dijkstra(int s, int dis[], int vis[]){
    dis[s]=0;
    q.push(make_pair(-dis[s], s));
    while(!q.empty()){
        int now=q.top().second;
        q.pop();
        if(vis[now]){
            continue;
        }
        vis[now]=1;
        for(int i=0;i<e[now].size();i++){
            int v=e[now][i].first;
            if(!vis[v]&&dis[v]>dis[now]+e[now][i].second){
                dis[v]=dis[now]+e[now][i].second;
                q.push(make_pair(-dis[v], v));
            }
        }
    }
}

int main(){

    int n, m, k, x, y;scanf("%d%d%d", &n, &m, &k);
    for(int i=1; i<=k; i++){
        scanf("%d", &x);
        v.push_back(x);
    }
    for(int i=1; i<=m; i++){
        scanf("%d%d", &x, &y);
        e[x].push_back({y, 1});
        e[y].push_back({x, 1});
    }
    memset(vis, 0, sizeof(vis));
    memset(dis1, 7, sizeof(dis1));
    dijkstra(1, dis1, vis);

    memset(vis, 0, sizeof(vis));
    memset(dis2, 7, sizeof(dis2));
    dijkstra(n, dis2, vis);
    for(int i=0; i<v.size(); i++){
        d.push_back(dis2[v[i]]);
    }
    sort(d.begin(), d.end());
    int ans=0;
    for(int i=0; i<v.size(); i++){
        vector<int>::iterator p=upper_bound(d.begin(), d.end(), dis2[v[i]]);
        p--;
        if(p==d.begin()){
            continue;
        }
        p--;
        ans=max(dis1[v[i]]+(*p)+1, ans);
    }
    printf("%d\n", min(ans, dis1[n]));

    return 0;
}
相关标签: 最短路