luogu P4943 密室 |最短路

题目描述

密室被打开了。###

哈利与罗恩进入了密室，他们发现密室由n个小室组成，所有小室编号分别为：1,2,...,n。所有小室之间有m条通道，对任意两个不同小室最多只有一条通道连接，而每通过一条通道都需要Ci 的时间。

开始时哈利与罗恩都在编号为1的小室里，他们的目标是拯救金妮和寻找日记，但是他们发现金妮和日记可能在两个不同的小室里，为了尽快发现真相，他们决定以最少的时间到达两个目标小室。但是某些小室只有会与蛇对话的人才能进入，也就是只有哈利一个人可以进入。

现在，哈利告诉你密室的结构，请你计算他们到达两个目标小室的最短时间。

输入格式

第一行 n,m,k 表示有n个小室m条通道，k间小室只有哈利可以进入。

第二行 k 个数，表示只有哈利可以进入的小室的编号。（若k=0，不包含该行）

接下来m行，每行3个数：a,b,c 表示a小室与b小室之间有一条需要花费c时间的通道。

最后一行，两个数 x,y 表示哈利与罗恩需要去的小室的编号

输出格式

一行，输出一个数，表示到达两个密室的最短时间。

#include<bits/stdc++.h>

#define N 1000005

#define M 100005

#define QAQ 2147483647

using namespace std;

inline int read() {//快读

    int f=1,x=0;

    char ch;

    do {

        ch=getchar();

        if(ch=='-')f=-1;

    } while(ch<'0'||ch>'9');

    do {

        x=x*10+ch-'0';

        ch=getchar();

    } while(ch>='0'&&ch<='9');

    return f*x;

}

struct eat{

    int next,to,quan;

}a[N];

int head[M],cnt;

int n,m,k;

int d1[M],d2[M],d3[M];

inline void add(int x,int y,int z){//链式前向星

    a[++cnt].next=head[x];

    a[cnt].to=y;

    a[cnt].quan=z;

    head[x]=cnt;

}

struct node{

    int u,d;

    bool operator <(const node& rhs)const{

        return d>rhs.d;

    }

};

bool f[M];

void dj1(int s){

	for(int i=1;i<=n;i++)d1[i]=QAQ;

    d1[s]=0;

    priority_queue<node>Q;

    Q.push((node){s,0});

    while(!Q.empty()){

        node ch=Q.top();

        Q.pop();

        int u=ch.u;

        int d=ch.d;

        if(d!=d1[u])continue;

        for(int i=head[u];i;i=a[i].next){

            int x=a[i].to,y=a[i].quan;

            if(d1[u]+y<d1[x]){

                d1[x]=d1[u]+y;

                Q.push((node){x,d1[x]});

            }

        }

    }

}

void dj2(int s){

	for(int i=1;i<=n;i++)d2[i]=QAQ;

    d2[s]=0;

    priority_queue<node>Q;

    Q.push((node){s,0});

    while(!Q.empty()){

        node ch=Q.top();

        Q.pop();

        int u=ch.u;

        int d=ch.d;

        if(d!=d2[u])continue;

        for(int i=head[u];i;i=a[i].next){

            int x=a[i].to,y=a[i].quan;

            if(d2[u]+y<d2[x]){

                d2[x]=d2[u]+y;

                Q.push((node){x,d2[x]});

            }

        }

    }

}

void dj3(int s){

	for(int i=1;i<=n;i++)d3[i]=QAQ;

    d3[s]=0;

    priority_queue<node>Q;

    Q.push((node){s,0});

    while(!Q.empty()){

        node ch=Q.top();

        Q.pop();

        int u=ch.u;

        int d=ch.d;

        if(d!=d3[u])continue;

        for(int i=head[u];i;i=a[i].next){

            int x=a[i].to,y=a[i].quan;

            if(f[x])continue;

            if(d3[u]+y<d3[x]){

                d3[x]=d3[u]+y;

                Q.push((node){x,d3[x]});

            }

        }

    }

}

int main(){

    n=read();m=read();k=read();

    for(int i=1;i<=k;i++)f[read()]=1;

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

        int a=read(),b=read(),c=read();

        add(a,b,c);

        add(b,a,c);

    }

	int x,y;

    x=read();y=read();

    dj1(1);dj2(x);

	dj3(1);

 	int ans=1e9;

 	ans=min(ans,d1[x]+d2[y]);

 	ans=min(ans,d1[y]+d2[y]);

 	ans=min(ans,max(d1[x],d3[y]));

 	ans=min(ans,max(d3[x],d1[y]));

 	cout<<ans<<endl;

}

巴特西

luogu P4943 密室 |最短路

题目描述

密室被打开了。###

输入格式

输出格式

最新文章

热门文章