新年好(cqoi 2005)
题目描述
重庆城里有n个车站,m条双向公路连接其中的某些车站.每两个车站最多用一条公路连接,从任何一个车站出发都可以经过一条或者多条公路到达其他车站,但不同的路径需要花费的时间可能不同.在一条路径上花费的时间等于路径上所有公路需要的时间之和.
佳佳的家在车站1,他有五个亲戚,分别住在车站a,b,c,d,e.过年了,他需要从自己的家出发,拜访每个亲戚(顺序任意),给他们送去节日的祝福.怎样走,才需要最少的时间?
输入格式 :
第一行:n,m为车站数目和公路的数目.
第二行:a,b,c,d,e，为五个亲戚所在车站编号。
以下m行,每行三个整数x,y,t,为公路连接的两个车站编号和时间.
输出格式 :
仅一行,包含一个整数T,为最少的总时间.
样例输入 :
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
样例输出 :
21
数据规模与约定 :
1 ≤ n ≤ 500000, 1 ≤ m ≤ 1000000;
1 ≤ a, b, c, d, e ≤ n;
1 ≤ x, y ≤ n, 1 ≤ t ≤ 100;
题解 ： 最短路，全排列， 暴力出奇迹， (为什么好多人第一眼都会想到最小生成树，包括我， emmmmmm)
Code block
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;
const int Maxn = 50005;
struct node{
int to, w;
};
vector <node> V[Maxn];
int h[Maxn],cnt,a[10];
int dt[50];
int d[7][Maxn],vis[Maxn];
int n,m,ans=INF;
int inq[Maxn];
void spfa(int v0,int k) {
queue<int> q;
memset(inq, 0, sizeof(inq));
q.push(v0);
inq[v0]=1;
d[k][v0]=0;
while (!q.empty()) {
int x=q.front(); q.pop();
inq[x]=0;
for (int i = 0; i < V[x].size(); i++) {
int y=V[x][i].to;
int w=V[x][i].w;
if (d[k][y]>d[k][x]+w) {
d[k][y]=d[k][x]+w;
if (!inq[y]) {
inq[y]=1;
q.push(y);
}
}
}
}
}
void dfs(int k) {
if (k==6) {
int s=0;
for (int i = 1;i < 6;i++) {
s+=d[dt[i]][a[dt[i+1]]];
}
ans=min(ans,s);
return;
}
for (int i = 2;i <= 6;i++) {
if (!vis[i]) {
vis[i]=1;
dt[k+1]=i;
dfs(k+1);
vis[i]=0;
}
}
}
int main() {
scanf("%d%d",&n,&m);
for (int i = 2;i <= 6;i++) {
scanf("%d",&a[i]);
}
for (int i = 1;i <= m;i++) {
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
V[a].push_back((node){b,c});
V[b].push_back((node){a,c});
}
memset(d, INF, sizeof(d));
a[1]=1;
dt[1]=1;
for (int i = 1;i <= 6;i++) {
spfa(a[i],i);
}
dfs(1);
printf("%d",ans);
return 0;
}
|
