本文共 1714 字，大约阅读时间需要 5 分钟。

题目描述

给定一个n个点m条边的有向图，有k个标记点，要求从规定的起点按任意顺序经过所有标记点到达规定的终点，问最短的距离是多少。

输入

第一行5个整数n、m、k、s、t，表示点个数、边条数、标记点个数、起点编号、终点编号。
接下来m行每行3个整数x、y、z，表示有一条从x到y的长为z的有向边。
接下来k行每行一个整数表示标记点编号。

输出

输出一个整数，表示最短距离，若没有方案可行输出-1。

输入样例

3 3 2 1 11 2 12 3 13 1 123

输出样例

3

思路

建一个新图，包括所有必须走的点。点与点之间的距离为原图中的最短路。
然后dfs枚举这些必须去的点去的顺序。（因为点数很小）累计一下距离即可。

代码

#include<cstdio>#include<cstring> #include<queue>#include<iostream>using namespace std;long long l[60001],bjd[20],n,m,k,s,t,T,x,y,z,lk;long long ans = 10000000000,S[20][50001];bool B[60001];struct asdf{   	long long to,next,zz;} a[2000001];void spfa(long long startbh, long long startd){   	long long h;	queue<long long> Q;	Q.push(startd);	S[startbh][startd] = 0;	while(Q.size()){   		h = Q.front();		Q.pop();		for(long long i = l[h]; i; i = a[i].next)		  if(S[startbh][h] + a[i].zz < S[startbh][a[i].to]){   		  	  S[startbh][a[i].to] = S[startbh][h] + a[i].zz;		  	  Q.push(a[i].to);		  }	}}void init(){   	scanf("%lld%lld%lld%lld%lld", &n, &m, &k, &s, &t);	lk = k;	for(long long i = 1; i <= m; ++i){   		scanf("%lld%lld%lld", &x, &y, &z);		a[++T] = (asdf){   y, l[x], z}; l[x] = T; 	}	spfa(0, s);	spfa(k+1, t);	for(long long i = 1; i <= k; ++i){   		scanf("%lld", &bjd[i]);		spfa(i, bjd[i]);	}	bjd[0] = s;	for(long long i = 1; i <= k; ++i)	  if(bjd[i] == s || bjd[i] == t) --lk;}void dfs(long long d, long long deep, long long ss){   	if(deep == lk + 1){   		ans = min(ans, ss+S[d][t]);		return;	}	B[d] = 1;	for(long long i = 1; i <= k; ++i)	  if(B[i] == 0 && bjd[i]!=s && bjd[i]!=t && ss + S[d][bjd[i]] <= ans)	  	  dfs(i, deep+1, ss+S[d][bjd[i]]);	B[d] = 0;}int main(){   	memset(S,0x7f,sizeof(S));	init();	B[k+1] = 0;	dfs(0, 1, 0);	if(ans < 10000000000) printf("%lld",ans);	else printf("-1");} 

转载地址：http://krkg.baihongyu.com/