【NOIP2012模拟8.7】找位置
Description
Farmer John 想找一个最好的位置来建新农场，这样他每天可以少走些路。 FJ所在的区域，有N个城镇(1 <= N <= 10,000)。 城镇之间，有M(1 <= M <= 50,000)条双向路相连。 所有城镇都可以借助一些路相互连接。 FJ需要你的帮助来选择最合适建新农场的城镇。 K(1 <= K <= 5)个城镇中有超市，FJ每天都会去这些超市。 他计划每天从新农场出发，访问包含超市的K个城镇，然后返回新农场。 FJ可以按照任意的顺序访问这些超市。 FJ只会在N-K个城镇中，选择一个城镇来建新农场。因为其他城镇的房价，比较低一些。 如果他把农场建在最优的位置，而且尽可能明智的选择行走路线。 请帮FJ计算，他每天需要行走的路线长度。
Input
第1行：三个空格隔开的整数，N，M和K。 第2…1+K行：第i+1行包含一个整数，范围1…N，表示包含第i个超市的城镇。 每个超市在不同城镇。 第2+K…1+K+M行：每行包含三个空格隔开的整数，i，j(1 <= i，j <= N)，和L(1 <= L <= 1000)， 表示城镇i和城镇j之间存在一条长度为L的路。
Output
如果他把农场建在最优的位置，FJ每天需要行走的最短路线长度。
Sample Input
5 6 3 1 2 3 1 2 1 1 5 2 3 2 3 3 4 5 4 2 7 4 5 10
Sample Output
12
Hint
FJ在5号城镇建立农场。他每天的行走路线为5-1-2-3-2-1-5，路线长度为12
题解
水题 先预处理出每个超市到每个点的距离 因为超市只有5个，全排列枚举便利顺序，再枚举农场的位置
code
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define R register
using namespace std
;
const int N
=10010,M
=50010;
int n
,m
,k
,last
,ans
=0xfffffff,head
[N
],w
[M
*2],to
[M
*2],next
[M
*2],a
[9],dis
[6][N
],vis
[N
],bj
[N
],b
[9];
inline void read(R
int &x
){
x
=0;char ch
=getchar();
while(!isdigit(ch
))ch
=getchar();
while(isdigit(ch
))x
=(x
<<1)+(x
<<3)+(ch
^48),ch
=getchar();
}
struct Node
{int w
,pos
;};
struct node
{
int cnt
;
Node q
[M
*2];
void push(Node x
){
q
[++cnt
]=x
;
int y
=cnt
;
while(y
>1&&q
[y
].w
<q
[y
>>1].w
)
q
[0]=q
[y
],q
[y
]=q
[y
>>1],q
[y
>>1]=q
[0],y
>>=1;
}
Node
top(){return q
[1];}
void pop(){
q
[1]=q
[cnt
--];
int y
=1,x
;
while((y
*2<=cnt
&&q
[y
*2].w
<q
[y
].w
)||(y
*2<cnt
&&q
[y
*2+1].w
<q
[y
].w
)){
if(y
*2<cnt
&&q
[y
*2+1].w
<q
[y
*2].w
)x
=y
*2+1;
else x
=y
<<1;
q
[0]=q
[x
],q
[x
]=q
[y
],q
[y
]=q
[0],y
=x
;
}
}
}q
;
inline void add(int x
,int y
,int z
){to
[++last
]=y
,w
[last
]=z
,next
[last
]=head
[x
],head
[x
]=last
;}
inline void dij(int x
){
memset(vis
,0,sizeof vis
);
dis
[x
][a
[x
]]=0,q
.cnt
=0,q
.push(Node
{0,a
[x
]});
while(true){
while(q
.cnt
&&vis
[q
.top().pos
])q
.pop();
if(!q
.cnt
)break;
Node y
=q
.top();
vis
[y
.pos
]=1;
for(R
int i
=head
[y
.pos
];i
;i
=next
[i
])
if(dis
[x
][to
[i
]]>y
.w
+w
[i
])
dis
[x
][to
[i
]]=y
.w
+w
[i
],q
.push(Node
{dis
[x
][to
[i
]],to
[i
]});
}
}
void dfs(int s
){
if(s
>k
){
int mi
=0x7ffffff,tot
=0;
for(R
int i
=1;i
<k
;++i
)tot
+=dis
[b
[i
]][a
[b
[i
+1]]];
for(R
int i
=1;i
<=n
;++i
)
if(!bj
[i
])mi
=min(mi
,dis
[b
[1]][i
]+dis
[b
[k
]][i
]);
for(R
int i
=1;i
<=k
;++i
)printf("%d ",b
[i
]);
printf("%d\n",tot
);
ans
=min(ans
,tot
+mi
);
}else
for(R
int i
=1;i
<=k
;++i
)
if(!vis
[i
])vis
[i
]=1,b
[s
]=i
,dfs(s
+1),vis
[i
]=0;
}
int main(){
R
int x
,y
,z
;
read(n
),read(m
),read(k
);
for(R
int i
=1;i
<=k
;++i
)read(a
[i
]),bj
[a
[i
]]=i
;
for(R
int i
=1;i
<=m
;++i
){
read(x
),read(y
),read(z
);
add(x
,y
,z
),add(y
,x
,z
);
}
memset(dis
,0x3f,sizeof dis
);
for(R
int i
=1;i
<=k
;++i
)dij(i
);
for(R
int i
=1;i
<=k
;++i
)vis
[i
]=0;
dfs(1);
printf("%d",ans
);
}
