Description

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

Input

第一行5个整数n、m、k、s、t，表示点个数、边条数、标记点个数、起点编号、终点编号。

接下来m行每行3个整数x、y、z，表示有一条从x到y的长为z的有向边。

接下来k行每行个整数表示标记点编号。

Output

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

Sample Input

3 3 2 1 1

1 2 1

2 3 1

3 1 1

2

3

Sample Output

3

HINT

【样例解释】

路径为1->2->3->1。

【数据范围】

20%的数据n<=10。

50%的数据n<=1000。

另有20%的数据k=0。

100%的数据n<=50000，m<=100000，0<=k<=10，1<=z<=5000。

代码如下：

#include<bits/stdc++.h>
#define Inf 0x3f3f3f3f3f3f3f3f
#define ll long long
using namespace std;

const int M = 100005 ,N = 50005;
int n ,m ,k ,s ,t ,head[N] ,cnt ,st[15];
ll ans = Inf ,dist[15][N];
bool vis[N] ,vist[15];
struct Edge {
    int to ,nxt;
    ll w;
    bool operator < (const Edge &a) const {
        return a.w < w;
    }
}edge[M];

void add(int from ,int to ,ll w) {
    edge[++cnt] = {to ,head[from] ,w};
    head[from] = cnt;
}
//head数组初值为-1

void Dijkstra(int id ,int idx) {
    priority_queue<Edge> q;
    memset(vis ,0 ,sizeof(vis));
    dist[id][idx] = 0;
    q.push(Edge{idx ,-1 ,0});
    while(q.empty()) {
        Edge now = q.top();
        q.pop();
        if(vis[now.to]) continue;
        vis[now.to] = 1;
        for(int i = head[now.to];i != -1;i = edge[i].nxt) {
            int to = edge[i].to;
            ll w = edge[i].w;
            if(dist[id][to] > dist[id][now.to] + w) {
                dist[id][to] = dist[id][now.to] + w;
                if(!vis[to])
                    q.push(Edge{to ,-1 ,dist[id][to]});
            }
        }
    }
}

void dfs(int u ,int now ,ll ct) {
    if(now == k) {
        cnt += dist[u][t];
        ans = min(ans ,ct);
        return;
    }
    for(int i = 1;i <= k;i++) {
        if(!vist[i]) {
            vist[i] = 1;
            dfs(i ,now + 1 ,ct + dist[u][st[i]]);
            vist[i] = 0;
        }
    }
}

int main() {
    memset(dist ,Inf ,sizeof(dist));
    memset(head ,-1 ,sizeof(head));
    scanf("%d%d%d%d%d" ,&n ,&m ,&k ,&s ,&t);
    for(int i = 1;i <= m;i++) {
        int x ,y ,z;
        scanf("%d%d%d" ,&x ,&y ,&z);
        add(x ,y ,z);
    }
    for(int i = 1;i <= k;i++) {
        scanf("%d" ,&st[i]);
        Dijkstra(i ,st[i]);
    }
    Dijkstra(k + 1 ,s);
    if(k == 0 || dist[k + 1][t] == Inf) {
        dist[k + 1][t] == Inf ? printf("-1") : printf("%lld" ,dist[k + 1][t]);
        return 0;
    }
    dfs(k + 1 ,0 ,0);
    printf("%lld" ,ans);
    return 0;
}