CodeForces1307D 最短路

题意

Cgg正在农场放牧，该农场由n个由m条双向道路连接的田地组成。目前Cgg在1号田地，并将在一天结束时到达位于第n号田地的家。
出于对农场发展的考虑，小黄毛牛头人协会命令Cgg铺设一条额外的双向道路。其中该农场有k个特殊田地，Cgg决定在两个不同的特殊田地之间安装道路。
注意，Cgg可以在已经连接两个特殊字段之间添加道路。（即允许创建重边）
添加道路后，Cgg将沿着从1号田地到n号田地的最短路径返回家中。由于Cgg的牛需要更多的运动，因此Cgg必须最大限度地增加这条最短路径的长度。帮帮他！

解法

容易想到求出所有的special点到1和N的最短路dis1和dis2，然后从中选出两个点i，j加上边之后，就会形成一条新的“可能的最短路”长度DIS = min(dis1[i],dis2[j]) + 1 + min(dis2[i],dis2[j])
题目转化为找出其中最大的点对使得DIS最大，观察式子发现可以将dis1从小到大排序，然后求出一个dis2的后缀最大值，就可以O(n)算出来

代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define fi first
#define se second
#define PII pair<int,int>
#define PLL pair<long long,long long>
#define mp make_pair
const int maxn = 2e5 + 10;
const int maxm = 31630;
int N,M,K;

struct Edge{
    int to,next;
}edge[maxn * 2];
int head[maxn],tot;
void init() {
    for(int i = 0 ; i <= N ; i ++) head[i] = -1;
    tot = 0;
}
void add(int u,int v){
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}
const int INF = 0x3f3f3f3f;
struct SpNode {
    int id;
    int dis1,dis2;
    SpNode(){}
    SpNode(int id, int dis1, int dis2):id(id),dis1(dis1),dis2(dis2){}
};
vector<SpNode> sp;
int dis[maxn];
struct node {
    int pos,val;
    node(int pos,int val):pos(pos),val(val){}
    friend bool operator < (node a,node b) {
        return a.val > b.val;
    }
};
void Dijkstra(int s) {
    for(int i = 0; i <= N ; i ++) dis[i] = INF;
    dis[s] = 0;
    priority_queue<node>Q;
    Q.push(node(s,0));
    while(!Q.empty()) {
        node u = Q.top(); Q.pop();
        if(u.val > dis[u.pos]) continue;
        for(int i = head[u.pos]; ~i; i = edge[i].next) {
            int v = edge[i].to;
            if(dis[v] > 1 + u.val) {
                dis[v] = 1 + u.val;
                Q.push(node(v,dis[v]));
            }
        }
    }
}
bool cmp(SpNode a,SpNode b){
    return a.dis1 < b.dis1;
}
int preMax[maxn];
int main(){
    scanf("%d%d%d",&N,&M,&K); init();
    for(int i = 1; i <= K; i ++) {
        int x; scanf("%d",&x);
        sp.push_back(SpNode(x,0,0));
    } 
    for(int i = 1; i <= M ; i ++) {
        int u,v; scanf("%d%d",&u,&v);
        add(u,v), add(v,u);
    }
    Dijkstra(1);
    for(int i = 0 ; i < sp.size(); i ++) {
        sp[i].dis1 = dis[sp[i].id];
    }
    Dijkstra(N);
    int ans = dis[1];
    for(int i = 0 ; i < sp.size(); i ++) {
        sp[i].dis2 = dis[sp[i].id];
    }
    sort(sp.begin(),sp.end(),cmp);
    int tmp = 0;
    for(int j = sp.size() - 1; j >= 0; j--) {
        preMax[j] = max(preMax[j + 1], sp[j].dis2);
    }
    for(int i = 0 ; i < sp.size() - 1; i ++) {
        tmp = max(tmp,sp[i].dis1 + min(sp[i].dis2, preMax[i + 1]) + 1);
    }
    printf("%d", min(ans,tmp));
    return 0;
}