介于本场比赛题目难度并不按照难度顺序排列，所以题解顺序不同。
需要题面或数据可以私聊我QQ（不一定在）：468170499.
T3：最短路（path）
Describe:
给定一个n个点m条边的有向图，有k个标记点，要求从规定的起点按任意顺序经过所有标记点到达规定的终点，问最短的距离是多少。
Hint:
20%的数据n<=10。
50%的数据n<=1000。
另有20%的数据k=0。
100%的数据n<=50000，m<=100000，0<=k<=10，1<=z<=5000。
解题思路：
我在考场上写这道题的时候，一眼没看出来。在最后看了一眼数据，发现k<=10，那么答案就非常显然了。我们可以把标记点为起点跑一边最短路。我感觉可能会卡SPFA（然而出题人很凉心），所以就写了一个堆优化的Dijkstra。时间复杂度为O(log(N + M) * N * K)（我习惯变量用小写）。因为k很小，所以我们可以枚举所有的方案，再跑一层k的循环判断。时间复杂度为(K! * K)，勉强不会超时，可以写状态压缩优化成O(2^K * K)，因为这道题暴力能过，所以就没写。这道题我在考场上是只过了一个样例，之后九分。主要是没看清题，有向图连了无向边。还有dis数组因为不能开到n方的大小，所有有一维应该要存点的编号，然后我在这里好像弄错了一点什么。。。
Code：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 50500, M = 202000, K = 11; int n, m, k, s, t; int tot = 0, Link[M], Next[M], to[M]; ll w[M]; inline int read() { int num = 0; bool flag = 1; char c = getchar(); for (; c < ‘0‘ || c > ‘9‘; c = getchar()) if (c == ‘-‘) flag = 0; for (; c >= ‘0‘ && c <= ‘9‘; c = getchar()) num = (num << 3) + (num << 1) + c - 48; return flag ? num : -num; } inline ll readll() { ll num = 0; bool flag = 1; char c = getchar(); for (; c < ‘0‘ || c > ‘9‘; c = getchar()) if (c == ‘-‘) flag = 0; for (; c >= ‘0‘ && c <= ‘9‘; c = getchar()) num = (num << 3) + (num << 1) + c - 48; return flag ? num : -num; } inline void add(int x, int y, ll z) { Next[++ tot] = Link[x]; Link[x] = tot; to[tot] = y; w[tot] = z; } // dis[i][j]表示从point[i]号节点为起点到j的最短距离 ll minn = LLONG_MAX; int ans[N], point[N]; bool use[K]; ll dis[K][N]; bool vis[K][N]; void dij(int start) { priority_queue < pair < ll, int> > q; for (int i = 1; i <= n; ++ i) dis[start][i] = 1e15, vis[start][i] = 0; dis[start][point[start]] = 0; q.push(make_pair(0, point[start])); for(; q.size(); ) { int x = q.top().second; q.pop(); if (vis[start][x]) continue; vis[start][x] = 1; for(int i = Link[x]; i; i = Next[i]) { int y = to[i], z = w[i]; if (dis[start][y] > dis[start][x] + z) { dis[start][y] = dis[start][x] + z; q.push(make_pair(-dis[start][y], y)); } } } } void dfs(int depth) { if (depth == k + 1) { ll sum = 0; sum += dis[0][point[ans[1]]]; for (int i = 1; i < k; ++ i) sum += dis[ans[i]][point[ans[i + 1]]]; sum += dis[ans[k]][t]; minn = min(minn, sum); } for (int i = 1; i <= k; ++ i) if (!use[i]) { use[i] = 1; ans[depth] = i; dfs(depth + 1); use[i] = 0; } } int main() { freopen("path.in", "r", stdin); freopen("path.out", "w", stdout); n = read(), m = read(), k = read(), s = read(), t = read(); for (int i = 1; i <= m; ++ i) { int x = read(), y = read(); ll z = readll(); add(x, y, z); } point[0] = s; dij(0); for (int i = 1; i <= k; ++ i) { int sign = read(); point[i] = sign; dij(i); } dfs(1); if (minn == 1e15) puts("-1"); else printf("%lld\n", minn); return 0; }
原文：https://www.cnblogs.com/ckn1023/p/10420195.html