P4943 密室（Dijkstra+堆优化）

# 密室

## 题目背景

NOIP2018 原创模拟题 T2

NOIP DAY1 T2 or DAY2 T2 难度

题目背景改编自小说《哈利波特与密室》。

## 题目描述

**密室被打开了。**

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

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

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

## 输入格式

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

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

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

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

## 输出格式

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

AC code

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
int limit[55000];
int head[200000],nextv[200000],edge[200000],var[200000];
int tot=0;
int n,m,k,t;
int x,y,z;
int r1,r2;
int r1_A,r2_B,r1_B,r2_A,bet;
priority_queue< pair<int ,int > > map;
int dest[55000];
bool visited[55000];
void add(int x,int y,int z){
	tot++;
	var[tot]=y;
	edge[tot]=z;
	nextv[tot]=head[x];
	head[x]=tot;
}
int dijkstra(int s,int p){
	memset(visited,false,sizeof(visited));
	memset(dest,0x3f3f3f,sizeof(dest));
	dest[s]=0;
	map.push(make_pair(0,s));
	while(!map.empty()){
		int num=map.top().second;
		map.pop();
		if(visited[num]==true)continue;
		visited[num]=true;
		for(int e=head[num];e!=0;e=nextv[e]){
			if(dest[var[e]]>dest[num]+edge[e] && (p==1 || p==3|| (p==2 && limit[var[e]]==false))){
				dest[var[e]]=dest[num]+edge[e];
				map.push(make_pair(-dest[var[e]],var[e]));
			}
		}
	}
	if(p==1){
		r1_A=dest[r1];
		r2_A=dest[r2];
	}
	else if(p==2){
		r1_B=dest[r1];
		r2_B=dest[r2]; 
	}
	else if(p==3){
		bet=dest[r2];
	}
} 
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(register int i=0;i<k;i++){
		scanf("%d",&t);
		limit[t]=true;
	}
	for(register int i=0;i<m;i++){
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	scanf("%d%d",&r1,&r2);
	dijkstra(1,1);
    dijkstra(1,2);
    dijkstra(r1,3);
	int mini=min(max(r1_A,r2_B),min(max(r1_B,r2_A),min(r1_A,r2_A)+bet));
	printf("%d",mini);
	return 0;
}