汕头市队赛 SRM 08 C

C-3 SRM 08

描述

给一个图，n 个点 m 条双向边，每条边有其长度。n 个点中有 k 个是特殊点，问任意两个特殊点的最短路是多少。

输入格式

第一行三个整数 n m k

第二行 k 个整数 $A_i$ ，为各个特殊点

接下来 m 行，每行三个整数 x y d，表示 x 到 y 有一条长度为 d 的边

输出格式

一个整数

样例输入

样例输出

数据范围与约定

图为联通图
$1 leq A_i,x,y leq n$
$1 leq d leq 10000$
$2 leq n leq 100000$
$n-1 leq m leq 300000$
$2 leq k leq 10000$

样例解释

样例中，1-3 的最短路为 7，3-5 的最短路为 9，1-5 的最短路为 16，因此答案为最小值 7

这道题对我来说有点难啊想了半天只会跑k-1次最短路最后在大爷的帮助下还是写出来了果然自己还是过于蒟蒻QAQ

这道题呢我的写法是将所有的关键点以0作为初始距离扔进优先队列里面跑一遍Dijkstra

记录每个点最近的关键点以及到关键点的距离（dis）

最后枚举边如果两端的点的最近关键点不一样就更新一波答案

下面证明写法的正确性

我们在跑最短路的时候顺便记录一下每个点是从哪个点扩展来的

首先显然答案不可能比真实的答案偏小所以证明如果答案存在则一定能找到

设一个最优解a——b——c——d，a,d为关键点，

1. dis(a,b)<=dis(a,d)/2

2. dis(c,d)<=dis(a,d)/2

（证明b,c之间有边）

如果因为等距离的问题 b,c 的最近关键点不是 a,d, 那么只要 b,c 的最近关键点不同，仍可得到答案

如果 b,c 的最近关键点相同设这个点为x，那么令 x!=a

那么 dis(a,x)=dis(a,b)+dis(b,x)<=dis(a,b)+dis(b,c)+dis(c,x)=dis(a,b)+dis(b,c)+dis(c,d)

可见 a——b——x 不比 a——b——c——d 差，

如果两个都是最优解那么由于dis(a,b)==dis(b,x)==dis(a,d)/2

设 a到b路径上最靠近b的点为 e 则dis(e,a)<dus(a,b)=dis(b,x)

所以e的最近关键点不会是x ，那么 （e的最近关键点）——e——b————x这条路同上面两条一样是另一个最优解且能由e-b更新

证毕

然后就贴一波代码咯 2333

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int M=1e5+7,inf=1e9+7;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
int n,m,k,p[M],dis[M],blong[M];
int cnt,first[M],ans=inf,h[M];
struct note{int to,from,next,w;}e[7*M];
void ins(int a,int b,int w){cnt++; e[cnt].to=b; e[cnt].from=a; e[cnt].next=first[a]; e[cnt].w=w; first[a]=cnt;}
void insert(int a,int b,int w){ins(a,b,w); ins(b,a,w);}
struct node{
    int d,pos;
    bool operator <(const node& x)const{return x.d<d;}
};
priority_queue<node>q;
void dj(){
    for(int i=1;i<=n;i++) dis[i]=inf;
    for(int i=1;i<=k;i++){
        int now=p[i];
        blong[now]=now; dis[now]=0;
        q.push((node){0,now});
    }
    while(!q.empty()){
        node y=q.top(); q.pop();
        int x=y.pos;
        if(y.d>dis[x]) continue;
        for(int i=first[x];i;i=e[i].next){
            int now=e[i].to;
            if(dis[now]>dis[x]+e[i].w){
                dis[now]=dis[x]+e[i].w;
                blong[now]=blong[x];
                q.push((node){dis[now],now});
            }
        }
    }
}
int main()
{
    int x,y,w;
    n=read(); m=read(); k=read();
    for(int i=1;i<=k;i++) p[i]=read(),h[p[i]]=1;
    for(int i=1;i<=m;i++){
        x=read(); y=read(); w=read();
        insert(x,y,w); if(h[x]&&h[y]) ans=min(ans,w);
    }//printf("%d
",ans);
    dj();
    for(int i=1;i<=cnt;i+=2) 
     if((!h[e[i].to]||!h[e[i].from])&&blong[e[i].from]!=blong[e[i].to]) 
      ans=min(ans,dis[e[i].from]+dis[e[i].to]+e[i].w);
    printf("%d
",ans);
    return 0;
}

View Code