题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6166
题意：
给出一个n个点的有向图。然后给你k个点，求这k个点任意两点之间的最短路的最小值。
思路：
以这k个点为起点，维护每个点的最短路和次短路，并且，次短路的祖先不能是本身。
先给几组样例：
5
5 6
1 2 100
2 5 100
5 1 100
3 2 100
2 4 1
4 3 1
2
1 3
5 6
1 2 100
2 5 100
5 1 100
3 2 100
2 4 1
4 3 1
2
1 3
4 5
1 3 1
3 1 1
1 2 1000
2 4 1
4 2 1
2
1 2
3 4
1 2 100
2 3 50
1 3 1
3 1 1
2
1 2
5 6
1 2 1
2 3 3
3 1 3
2 5 1
2 4 2
4 3 1
3
1 3 5
Case #1: 102
Case #1: 102
Case #3: 1000
Case #4: 51
Case #5: 2
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF = 1e15;
const int maxn = 1e5 + ;
int T, N, M, k;
queue<int>que;
struct Edge
{
int to, next, len;
Edge() {}
Edge(int to, int next, int len): to(to), next(next), len(len) {}
} E[maxn * ];
int head[maxn], tot;
void initEdge()
{
for(int i = ; i <= N; i++) head[i] = -;
tot = ;
}
void addEdge(int u, int v, int len)
{
E[tot] = Edge(v, head[u], len);
head[u] = tot++;
}
LL dis[maxn][];
int ant[maxn][];
bool in[maxn], qr[maxn];
int main ()
{
int ic = ;
scanf("%d", &T);
while(T--)
{
scanf("%d %d", &N, &M);
initEdge();
for(int i = ; i <= M; i++)
{
int u, v, len;
scanf("%d %d %d", &u, &v, &len);
addEdge(u, v, len);
}
for(int i = ; i <= N; i++)//init
{
dis[i][] = dis[i][] = INF;
ant[i][] = ant[i][] = -;
in[i] = qr[i] = false;
}
queue<int>que;
scanf("%d", &k);
for(int i = ; i <= k; i++)
{
int v;
scanf("%d", &v);
dis[v][] = ;
ant[v][] = v;
que.push(v), qr[v] = in[v] = true;
}
while(!que.empty())
{
int u = que.front();
in[u] = false,que.pop();
for(int k = head[u]; ~k; k = E[k].next)
{
int v = E[k].to;
LL len = (LL)E[k].len + dis[u][];
bool update = false;
if(len < dis[v][])
{
dis[v][] = len;
ant[v][] = ant[u][];
update = true;
}
else if (len < dis[v][] && ant[u][] != v)
{
dis[v][] = len;
ant[v][] = ant[u][];
update = true;
}
len = (LL)E[k].len + dis[u][];
if (len < dis[v][] && ant[u][] != v)
{
dis[v][] = len;
ant[v][] = ant[u][];
update = true;
}
if(update&&!in[v])
{
que.push(v);
in[v] = true;
}
}
}
LL ans = INF;
for(int i=;i<=N;i++)
if(qr[i]) ans = min(ans,dis[i][]);
printf("Case #%d: %lld\n", ++ic, ans);
}
return ;
}