D 自由世界

D 自由世界

思路很简单，先给每个点跑一遍最短路，记录到的路径长度。再去管传送门，从每个传送门这跑一遍最短路，记录传送门到的路径，和取个最小值即可。

我一开始为了图个方便，把传送门和每个点都建了个边权为的边，导致凭空多出来至少条边，就T了，呜呜呜。。。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+10;
const int inf=0x3f3f3f3f;
struct sa{
    int dis;
    int pos;
};
bool operator <(const sa &a,const sa &b) { return a.dis>b.dis; }

priority_queue<sa>q;


struct Edge
{
    int u, v, w, next;
}edge[N<<2];
int head[N];
int cnt;
void add_edge(int u, int v, int w)
{
    edge[cnt].u = u;
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}


int dis[N];
bool vis[N];
int n,m,s,t,u,v,w,T,k;

void dij(int s,int v,int d[]){
    memset(vis,0,sizeof(vis));
    for (int i=1;i<=n;i++) d[i] = inf;
    d[s]=v;
    q.push( (sa) {v,s});
    while(!q.empty())
    {
        sa ns=q.top();
        q.pop();
        int x=ns.pos;
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x]; i!=-1 ; i=edge[i].next)
        {
            int to=edge[i].v;
            int dd=d[x]+edge[i].w;
            if(d[to]>dd)
            {
                d[to]=dd;
                q.push( (sa) {d[to],to});
            }
        }
    }
}
int cnt1[N];
int main()
{

    memset(head,-1,sizeof(head));
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 1 ;i <= m ;i++){
        scanf("%d%d%lld",&u,&v,&w);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    for(int i = 1 ;i <= n - 1 ;i++){
        dij(i, 0, dis);
        cnt1[i + 1] = dis[i + 1];
    }
    for(int i = 1 ;i <= k; i++){
        scanf("%d",&u);
        dij(u , 0 , dis);
        for(int j = 1 ;j <= n - 1; j++){
           cnt1[j + 1] = min( cnt1[j + 1] , dis[j + 1]);
        }
    }
    long long ans = 0;
    for (int i = 2; i <= n; i++) {
        ans += cnt1[i];
    }
    printf("%lld",ans);
    return 0;
}