洛谷P5764 新年好

传送门

题目描述

重庆城里有 nn 个车站，mm 条双向公路连接其中的某些车站。每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路径上花费的时间等于路径上所有公路需要的时间之和。

佳佳的家在车站 11，他有五个亲戚，分别住在车站 a,b,c,d,ea,b,c,d,e。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？

输入格式

第一行：n,mn,m，分别为车站数目和公路的数目。

第二行：a,b,c,d,ea,b,c,d,e，分别为五个亲戚所在车站编号。

以下 mm 行，每行三个整数 x,y,tx,y,t，为公路连接的两个车站编号和时间。

输出格式

仅一行，包含一个整数 TT，为最少的总时间。保证 T\le 10^9T≤10
9
。

输入输出样例

输入 #1复制
6 6
2 3 4 5 6
1 2 8
2 3 3
3 4 4
4 5 5
5 6 2
1 6 7
输出 #1复制
21

说明/提示

对于 40%40% 的数据，有 1≤n≤5001≤n≤500，1≤m≤20001≤m≤2000。

对于 100%100% 的数据，有 1≤n≤500001≤n≤50000，1≤m≤1000001≤m≤100000，1\le a,b,c,d,e≤n1≤a,b,c,d,e≤n，1≤x,y≤n1≤x,y≤n，1≤t≤100001≤t≤10000。

上代码：

#include
#include
#include
#include
#define inf 0x7fffffff
using namespace std;
bool used[50005],searchUsed[10];
struct Edge{
	int v,value;
	bool operator <(const Edge &a) const {return this->value>a.value;}
};
priority_queue<Edge> Q;
vector<Edge> G[50005];
int n,m,par[10],dis[10][50005],ans=0x7fffffff;
void Empty(){while(Q.size())	Q.pop();}
void Dijkstra(int u)
{
	Empty();
	memset(used,false,sizeof used);
	for(int i=1;i<=n;++i)	dis[u][i]=inf;
	dis[u][par[u]]=0;
	Q.push((Edge){par[u],0});
	while(Q.size())
	{
		Edge now=Q.top();
		Q.pop();
		int where=now.v;
		if(used[where])	continue;
		used[where]=true;
		for(unsigned long i=0;i<G[where].size();++i)	if(dis[u][where]+G[where][i].value<dis[u][G[where][i].v])	dis[u][G[where][i].v]=dis[u][where]+G[where][i].value,Q.push((Edge){G[where][i].v,dis[u][G[where][i].v]});
	}
}//判断起点，进行分别最短路。这里用的dijkstra
void Search(int tot,int value,int now)
{
	if(tot==5)
	{
		ans=min(ans,value);
		return ;
	}
	for(int i=1;i<=5;++i)	if(!searchUsed[i])	searchUsed[i]=true,Search(tot+1,dis[now][par[i]]+value,i),searchUsed[i]=false;
}//我们以1为起点，进行搜索。
int main(){
	scanf("%d %d",&n,&m);
	scanf("%d %d %d %d %d",&par[1],&par[2],&par[3],&par[4],&par[5]);
	par[0]=1;
	for(int i=1,u,v,value;i<=m;++i)	scanf("%d %d %d",&u,&v,&value),G[u].push_back((Edge){v,value}),G[v].push_back((Edge){u,value});
	Dijkstra(0);
	Dijkstra(1);
	Dijkstra(2);
	Dijkstra(3);
	Dijkstra(4);
	Dijkstra(5);//六次dijkstra
	Search(0,0,0);
	printf("%d",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56