记录编号	447405	评测结果	AAAAAAAAAA
题目名称	[省常中2011S4] starhder的旅游	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.098 s
提交时间	2017-09-10 10:22:26	内存使用	0.82 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

inline char getc(void) { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int read(void) { 
    register char tmp = getc();
    register int res = 0;
    while(!isdigit(tmp)) tmp = getc();
    while(isdigit(tmp))
        res = ((res + (res << 2)) << 1) + (tmp ^ 0x30),
        tmp = getc();
    return res;
}

#define MAXN (210)
#define MAXT (11)
#define INF (0x7fffffff)

int N, M, T;
int q[MAXT], f[MAXT][1<<MAXT];
int dis[MAXN][MAXN], full;

int main() { 
#ifndef LOCAL
    freopen("starhder.in", "r", stdin);
    freopen("starhder.out", "w", stdout);
#endif
    memset(dis, 0x3f, sizeof(dis));
    memset(f, 0x3f, sizeof(f));
    for(int i = 0; i < MAXN; ++i) 
        dis[i][i] = 0;
    N = read(), M = read(), T = read() + 1;
    q[0] = 1, full = (1 << T) - 1;
    for(int i = 1; i < T; ++i) 
        q[i] = read();
    for(int i = 0, a, b; i < M; ++i) { 
        a = read(), b = read();
        dis[a][b] = dis[b][a] = read();
    }
    for(int k = 1; k <= N; ++k) 
        for(int i = 1; i <= N; ++i) 
            for(int j = 1; j <= N; ++j) 
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    f[0][1] = 0;
    for(int i = 1; i <= full; i += 2) 
        for(int j = 1; j < T; ++j) 
            if(i & (1 << j)) continue;
            else for(int k = 0; k < T; ++k)
                if(i & (1 << k)) 
                    f[j][i|(1<<j)]=\
                    min(f[j][i|(1<<j)], f[k][i]+dis[q[k]][q[j]]);
    int ans = INF;
    for(int i = 1; i < T; ++i) 
        ans = min(ans, f[i][full]+dis[q[i]][N]);
    printf("%d\n", ans);
}