欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JZOJ 3470. 【NOIP2013模拟联考8】最短路(path)

程序员文章站 2022-06-26 09:56:57
470. 【NOIP2013模拟联考8】最短路(path) (Standard IO) Time Limits: 1000 ms Memory Limits: 262144 KB Detailed Limits 470. 【NOIP2013模拟联考8】最短路(path) (Standard IO) ......

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。
 
 做法:对每一个特殊点做最短路,然后枚举经过最短路的顺序。
 
JZOJ 3470. 【NOIP2013模拟联考8】最短路(path)
 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <queue>
 5 #define N 100007
 6 #define largest 100000000007
 7 using namespace std;
 8 int n, m, k, s, t, spe[15], tot, ls[N], cnt;
 9 long long ans, dis[N], d[15][15];
10 bool b[N], v[40];
11 queue<int> q;
12 
13 struct edge
14 {
15     int to, next, w;
16 }e[N];
17 
18 void add(int x, int y, int z)
19 {
20     e[++tot].to = y;
21     e[tot].w = z;
22     e[tot].next = ls[x];
23     ls[x] = tot;
24 }
25 
26 void spfa(int x)
27 {
28     memset(b, 0, sizeof(b));
29     for (int i = 1; i <= n; i++)
30         dis[i] = largest;
31     dis[x] = 0;
32     q.push(x);
33     while (!q.empty())
34     {
35         int now = q.front();
36         q.pop();
37         for (int i = ls[now]; i; i = e[i].next)
38         {
39             if (dis[now] + e[i].w < dis[e[i].to])
40             {
41                 dis[e[i].to] = dis[now] + e[i].w;
42                 if (!b[e[i].to])
43                 {
44                     q.push(e[i].to);
45                     b[e[i].to] = 1;
46                 }
47             }
48         }
49         b[now] = 0;
50     }
51     cnt++;
52     for (int i = 1; i <= k + 1; i++)
53         if (cnt != i)    d[cnt][i] = dis[spe[i]]; 
54     d[cnt][k + 2] = dis[t];
55 }
56 
57 void dfs(int dep, long long sum, int dc)
58 {
59     if (sum + d[dc][k + 2] > ans)    return;
60     if (dep >= k + 1)
61     {
62         if (sum + d[dc][k + 2] < ans)    ans = sum + d[dc][k + 2];
63         return;
64     }
65     for (int i = 2; i <= k + 1; i++)
66         if (!v[i])
67         {
68             v[i] = 1;
69             dfs(dep + 1, sum + d[dc][i], i);
70             v[i] = 0;
71         }
72 }
73 
74 int main()
75 {
76     scanf("%d%d%d%d%d", &n, &m, &k, &s, &t);
77     for (int i = 1; i <= m; i++)
78     {
79         int x, y, z;
80         scanf("%d%d%d", &x, &y, &z);
81         add(x, y, z);
82     }
83     for (int i = 2; i <= k + 1; i++)
84         scanf("%d", &spe[i]);
85     spe[1] = s;
86     for (int i = 1; i <= k + 1; i++)
87         spfa(spe[i]);
88     ans = largest;
89     dfs(1, 0, s);
90     if (ans < largest)    printf("%lld", ans);
91     else printf("-1");
92 }
View Code