470. 【NOIP2013模拟联考8】最短路(path) (Standard IO)

Time Limits:  1000 ms  Memory Limits: 262144 KB  Detailed Limits  

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

【样例解释】

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

 

 

Data Constraint

20%的数据n<=10。

50%的数据n<=1000。

另有20%的数据k=0。

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

 

  做法：对每一个特殊点做最短路，然后枚举经过最短路的顺序。

 

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#define N 100007
#define largest 100000000007
using namespace std;
int n, m, k, s, t, spe[15], tot, ls[N], cnt;
long long ans, dis[N], d[15][15];
bool b[N], v[40];
queue<int> q;

struct edge
{
    int to, next, w;
}e[N];

void add(int x, int y, int z)
{
    e[++tot].to = y;
    e[tot].w = z;
    e[tot].next = ls[x];
    ls[x] = tot;
}

void spfa(int x)
{
    memset(b, 0, sizeof(b));
    for (int i = 1; i <= n; i++)
        dis[i] = largest;
    dis[x] = 0;
    q.push(x);
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        for (int i = ls[now]; i; i = e[i].next)
        {
            if (dis[now] + e[i].w < dis[e[i].to])
            {
                dis[e[i].to] = dis[now] + e[i].w;
                if (!b[e[i].to])
                {
                    q.push(e[i].to);
                    b[e[i].to] = 1;
                }
            }
        }
        b[now] = 0;
    }
    cnt++;
    for (int i = 1; i <= k + 1; i++)
        if (cnt != i)    d[cnt][i] = dis[spe[i]]; 
    d[cnt][k + 2] = dis[t];
}

void dfs(int dep, long long sum, int dc)
{
    if (sum + d[dc][k + 2] > ans)    return;
    if (dep >= k + 1)
    {
        if (sum + d[dc][k + 2] < ans)    ans = sum + d[dc][k + 2];
        return;
    }
    for (int i = 2; i <= k + 1; i++)
        if (!v[i])
        {
            v[i] = 1;
            dfs(dep + 1, sum + d[dc][i], i);
            v[i] = 0;
        }
}

int main()
{
    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 = 2; i <= k + 1; i++)
        scanf("%d", &spe[i]);
    spe[1] = s;
    for (int i = 1; i <= k + 1; i++)
        spfa(spe[i]);
    ans = largest;
    dfs(1, 0, s);
    if (ans < largest)    printf("%lld", ans);
    else printf("-1");
}