JZOJ 3470. 【NOIP2013模拟联考8】最短路(path)
程序员文章站
2022-03-30 18:24:52
470. 【NOIP2013模拟联考8】最短路(path) (Standard IO) Time Limits: 1000 ms Memory Limits: 262144 KB Detailed Limits 470. 【NOIP2013模拟联考8】最短路(path) (Standard IO) ......
470. 【NOIP2013模拟联考8】最短路(path) (Standard IO)
Time Limits: 1000 ms Memory Limits: 262144 KB Detailed Limits
做法:对每一个特殊点做最短路,然后枚举经过最短路的顺序。
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 }