中转站，凑字

朴实无华的一天，国庆放假四天，我倒贴国庆两天来集训
今晚上又是主动想写博客的一天（
但是实在想不出写点什么，本人没有什么才华，也没有高超的技巧，就是个普普通通的信竞选手
最近上了高中，之前初中难理解的东西，现在也差不多能理解了，今天，没什么好说的，只解决了一题最短路的问题
题目是这样的:

题目描述
Kiana最近兼职起了快递工作，每天早上她都会从家里出发，先到中转站去接今天要送的快递清单，再将快递送到相应的地址去。

可乐城一共有n个地点，m条双向道路将这些地点连通，使得任意两个地点之间都能够通过道路相互到达。Kiana的家所在地点的编号为s，而由于可乐城快递业合理的工作区域划分机制，Kiana需要将快递送达的地址集中在一个地点上，其编号为t。同样仰仗于快递业的发达，城中共有k个地点设置了快递中转站，其中第i个地点的编号为ri。

因为交通状况可能不同，所以Kiana通过每条道路所需的时间是不同的，其中通过第i条道路所需的时间为ai。Kiana可以自己决定让快递公司将自己要送的快递运输到哪一个中转站去，使得她从家到中转站再从中转站到目的地所花的总时间尽可能少。

现在Kiana想知道，自己送快递所需的总时间最少是多少。由于Kiana自己不会算，所以希望你能够帮助她。

输入输出格式

第一行包含五个正整数n,m,s,t,k，分别表示可乐城中的地点数、双向道路数、Kiana的家所在的地点编号、送快递的目的地编号和可乐城中的中转站数量。

第二行包含k个正整数，其中第i个数ri表示第i个中转站的编号为ri。

接下来m行，其中第i行包含三个正整数ui,vi,ai，表示在地点ui和vi之间有一条双向道路，Kiana通过这条道路所需的时间为ai。

输入保证中转站的编号两两不同，任意两个地点之间至多只有一条双向道路，且没有一个地点和自己之间有道路。

输出共一行，包含一个非负整数，表示Kiana送快递所需的最少总时间。

输入输出样例
输入样例#1：

5 6 1 5 3
2 3 4
1 2 5
1 3 2
1 4 6
2 5 4
3 5 3
4 5 1

输出样例#1：

5

愚笨的我一开始并没有想到先从家跑一遍最短路然后从目的地再跑一遍最短路，然后枚举中间的中转站，我想到的是，从家跑一遍，然后再每个中转站都跑一遍，再算出最短距离，所以只a了六个点，现在搞定了

#include
using namespace std;
struct Edge
{
	int v;
	int w;
	int next;
}edge[7000];//链式前向星 
int num=0,now;
int head[7000],dis[2100][2100],vis[2100];
int zhong[3010];//dis【x】【y】即x到y的最短距离 
int n,m,s,t,k;
priority_queue, vector >, greater > >q;
//朴实无华的stl大根堆 
inline int dijikstra(int S)
{
	memset(vis,0,sizeof(vis));//将vis初始化
	
	dis[S][S]=0;//自己到自己的距离是零 
	q.push(make_pair(0,S));
	//把起点塞进去 
	while(!q.empty())
	{
		now=q.top().second;
		q.pop();
		//现在所处的位置 
		
		if(vis[now])continue;
		vis[now]=1;
		//如果走过这个点那就肯定不用再走一遍
		
		for (int i=head[now];i;i=edge[i].next)
		{//链式前向星的独特循环方式 
			int v=edge[i].v,w=edge[i].w;
			if(vis[v])continue;
			//走过的不必再走 
			if(dis[S][v]>w+dis[S][now])
			{
				dis[S][v]=w+dis[S][now];
				q.push(make_pair(dis[S][v],v));
			}
			//更新最短距离 
		} 
	}
}
int main()
{
	memset(dis,0x3f,sizeof(dis));//将dis初始化 
	
	cin>>n>>m>>s>>t>>k;
	if(n>3000||m>7000)cout<<666;
	for (int i=1;i<=k;i++)
	{
		cin>>zhong[i];
	}//记录中转站
	for (int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		num++;
		edge[num].v=v;
		edge[num].w=w;
		edge[num].next=head[u];
		head[u]=num;
		num++;
		edge[num].v=u;
		edge[num].w=w;
		edge[num].next=head[v];
		head[v]=num;
	}//存图
	 
	dijikstra(s);//先跑一遍从家出发的 
	
	for (int i=1;i<=k;i++)
	{
		dijikstra(zhong[i]);
	}//每个中转站都跑一遍 
	int mini=0x7fffffff;
	
	for (int i=1;i<=k;i++)
	{
		
		mini=min(mini,dis[s][zhong[i]]+dis[zhong[i]][t]);
	}//选出最小的那条 
	cout< 
一看就很笨比 
AC代码 
#include
using namespace std;
struct Edge
{
	int v;
	int w;
	int next;
}edge[510000];//链式前向星 
int num=0,now;
int head[510000],dis[210000],vis[210000],dis2[210000];
int zhong[210000];
int n,m,s,t,k;
priority_queue, vector >, greater > >q;
//朴实无华的stl大根堆 
inline int dijikstra(int S)
{
	memset(vis,0,sizeof(vis));//将vis初始化
	
	dis[S]=0;//自己到自己的距离是零 
	q.push(make_pair(0,S));
	//把起点塞进去 
	while(!q.empty())
	{
		now=q.top().second;
		q.pop();
		//现在所处的位置 
		
		if(vis[now])continue;
		vis[now]=1;
		//如果走过这个点那就肯定不用再走一遍
		
		for (int i=head[now];i;i=edge[i].next)
		{//链式前向星的独特循环方式 
			int v=edge[i].v,w=edge[i].w;
			if(vis[v])continue;
			//走过的不必再走 
			if(dis[v]>w+dis[now])
			{
				dis[v]=w+dis[now];
				q.push(make_pair(dis[v],v));
			}
			//更新最短距离 
		} 
	}
}

inline int dijikstra2(int S)
{
	memset(vis,0,sizeof(vis));//将vis初始化
	
	dis2[S]=0;//自己到自己的距离是零 
	q.push(make_pair(0,S));
	//把起点塞进去 
	while(!q.empty())
	{
		now=q.top().second;
		q.pop();
		//现在所处的位置 
		
		if(vis[now])continue;
		vis[now]=1;
		//如果走过这个点那就肯定不用再走一遍
		
		for (int i=head[now];i;i=edge[i].next)
		{//链式前向星的独特循环方式 
			int v=edge[i].v,w=edge[i].w;
			if(vis[v])continue;
			//走过的不必再走 
			if(dis2[v]>w+dis2[now])
			{
				dis2[v]=w+dis2[now];
				q.push(make_pair(dis2[v],v));
			}
			//更新最短距离 
		} 
	}
}

int main()
{
	memset(dis,0x3f,sizeof(dis));//将dis初始化 
	memset(dis2,0x3f,sizeof(dis));//将dis初始化 
	cin>>n>>m>>s>>t>>k;
	for (int i=1;i<=k;i++)
	{
		cin>>zhong[i];
	}//记录中转站
	for (int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		num++;
		edge[num].v=v;
		edge[num].w=w;
		edge[num].next=head[u];
		head[u]=num;
		num++;
		edge[num].v=u;
		edge[num].w=w;
		edge[num].next=head[v];
		head[v]=num;
	}//存图
	 
	dijikstra(s);//先跑一遍从家出发的 
	
	dijikstra2(t);//再反着跑一遍
	
	int mini=0x7fffffff;
	
	for (int i=1;i<=k;i++)
	{
		mini=min(mini,dis[zhong[i]]+dis2[zhong[i]]);
	}//选出最小的那条 
	cout< 
字数水的差不多了，先撤了