【洛谷P1828】香甜的黄油

题目大意：给定 N 个点，M 条边的无向图，在其中选定 P 个点，每个点可能被选多次，求图中的一个点到选定的 P 个点的距离的值最小是多少。

题解：由于数据范围的限制，直接 Floyd 会超时，因此对每个点做一次堆优化的 dij，统计答案贡献后更新答案即可。

代码如下

#include <bits/stdc++.h>

#define mp make_pair

using namespace std;

typedef pair<int,int> P;

const int maxn=810;

inline int read(){

    int x=0,f=1;char ch;

    do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));

    do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));

    return f*x;

}

struct node{

    int nxt,to,w;

}e[maxn<<2];

int tot=1,head[maxn];

inline void add_edge(int from,int to,int w){

    e[++tot]=node{head[from],to,w},head[from]=tot;

}

int num,n,m,pos[maxn],d[maxn];

bool vis[maxn];

priority_queue<P> q;

void read_and_parse(){

    num=read(),n=read(),m=read();

    for(int i=1;i<=num;i++)pos[i]=read();

    for(int i=1,x,y,z;i<=m;i++){

        x=read(),y=read(),z=read();

        add_edge(x,y,z),add_edge(y,x,z);

    }

}

void dij(int st){

    memset(d,0x3f,sizeof(d));

    memset(vis,0,sizeof(vis));

    d[st]=0,q.push(mp(0,st));

    while(q.size()){

        int u=q.top().second;q.pop();

        if(vis[u])continue;

        vis[u]=1;

        for(int i=head[u];i;i=e[i].nxt){

            int v=e[i].to,w=e[i].w;

            if(d[u]+w<d[v])d[v]=d[u]+w,q.push(mp(-d[v],v));

        }

    }

}

void solve(){

    int ans=0x3f3f3f3f;

    for(int i=1;i<=n;i++){

        dij(i);

        int tmp=0;

        for(int i=1;i<=num;i++)tmp+=d[pos[i]];

        ans=min(ans,tmp);

    }

    printf("%d\n",ans);

}

int main(){

    read_and_parse();

    solve();

    return 0;

}