题目描述
J 国有 n 座城市，这些城市之间通过 m 条单向道路相连，已知每条道路的长度。
一次，居住在 J 国的 Rainbow 邀请 Vani 来作客。不过，作为一名资深的旅行者，Vani 只对 J 国的 kk 座历史悠久、自然风景独特的城市感兴趣。
为了提升旅行的体验，Vani 想要知道他感兴趣的城市之间「两两最短路」的最小值（即在他感兴趣的城市中，最近的一对的最短距离）。
也许下面的剧情你已经猜到了——Vani 这几天还要忙着去其他地方游山玩水，就请你帮他解决这个问题吧。
输入格式
每个测试点包含多组数据，第一行是一个整数 T，表示数据组数。注意各组数据之间是互相独立的。
对于每组数据，第一行包含三个正整数 n,m,k表示 J 国的 n 座城市（从 1 \sim n1∼n 编号），m 条道路，Vani 感兴趣的城市的个数 k。
接下来 m 行，每行包括 3 个正整数 x,y,z，表示从第 xx 号城市到第 yy 号城市有一条长度为 z 的单向道路。注意 x,y 可能相等，一对 x,y 也可能重复出现。
接下来一行包括 k 个正整数，表示 Vani 感兴趣的城市的编号。
输出格式
输出文件应包含 T 行，对于每组数据，输出一个整数表示 k 座城市之间两两最短路的最小值。
输入输出样例
2
6 7 3
1 5 3
2 3 5
1 4 3
5 3 2
4 6 5
4 3 7
5 6 4
1 3 6
7 7 4
5 3 10
6 2 7
1 2 6
5 4 2
4 3 4
1 7 3
7 2 4
1 2 5 3
5
6
说明/提示
样例解释
对于第一组数据，1 到 3 最短路为5；1 到 6 最短路为 7；3,6 无法到达，所以最近的两点为 1,3，最近的距离为 5。
对于第二组数据，1 到 2 最短路为 6；5 到 3 最短路为 6；其余的点均无法互相达，所以最近的两点为 1,21,2和 5,3，最近的距离为 6。
数据范围
| 1 | 1,000≤1,000 | 5,000≤5,000 | 无 |
| 2 | 1,000≤1,000 | 5,000≤5,000 | 无 |
| 3 | 100,000≤100,000 | 500,000≤500,000 | 保证数据为有向无环图 |
| 4 | 100,000≤100,000 | 500,000≤500,000 | 保证数据为有向无环图 |
| 5 | 100,000≤100,000 | 500,000≤500,000 | 保证数据为有向无环图 |
| 6 | 100,000≤100,000 | 500,000≤500,000 | 无 |
| 7 | 100,000≤100,000 | 500,000≤500,000 | 无 |
| 8 | 100,000≤100,000 | 500,000≤500,000 | 无 |
| 9 | 100,000≤100,000 | 500,000≤500,000 | 无 |
| 10 | 100,000≤100,000 | 500,000≤500,000 | 无 |
思路：
这题的正解很高深，正解是O(nlogn),是来回跑两次Dijkstra，然后在染色什么的，还有一种要劣一点的就是按位是1还是0将其分为两堆，然后跑最短路，但我要说的是一个畜生算法，一个比BK201还要畜生的算法。
众所周知，Dijkstra就是一种贪心，在不停的放缩中求得最最优解，所以原题让我们求最小的，那我们可以一个一个去跑然后求得最小的，这很显然会T掉，但可以优化一下，每次跑完最小值后直接结束程序不就行了吗？
原题是让我们找最小距离，变化一下不就成了找最近的点吗？？？？Dijkstra的堆优化好像就有这样的性质，每次从堆顶取出一个元素，然后去跑，但堆顶的一定是最小的，所以当第一个出堆时，dis就已经确定，后面就不用跑了，自然万一图没有联通，最后就输出0x3f3f3f3f就可以了，
复杂度：
一下纯属玄学，可以直接跳过。
最快（暗指出题人不卡）O(m)的，但最坏，就会变成O（nlog n）感觉要慢很多但是思考一下两种情况
- 每遍访问到第 n−k 个点的时候，即：把所有的不感兴趣的点都访问过了。此时一定能找到一个感兴趣的点。而这种情况才是真的最坏情况。
- 假如我们构建出对于一个点，按照上面的情况让它需要把所有的不感兴趣的点都访问一遍，那么对于当前点确实是一个 (n-k)*log(n−k)的复杂度。但是我们会发现对于其他的点去再跑dijkstradijkstra的时候很难再跑到这个最坏复杂度。
这样似乎也挺快的。据说有人加了个快读，比STD还要快。。。。
代码
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<bitset>
using namespace std;
const int maxn=1e6+;
struct no
{
int to;
int next;
int value;
}way[maxn];
int tot,head[maxn];
int add(int x,int y,int w)
{
way[++tot].next=head[x];
way[tot].to=y;
way[tot].value=w;
head[x]=tot;
}
long long dis[maxn];
struct node
{
int u;
long long d;
bool operator < (const node &rhs) const
{
return d>rhs.d;
}
};
priority_queue<node> q;
bitset<maxn> vis,fl;
int n,m,k;
long long dijkstra(int st)
{
while(!q.empty())
{
q.pop();
}
vis.reset();
memset(dis,0x3f,sizeof(dis));
q.push((node){st,});
dis[st]=;
while(!q.empty())
{
node fi=q.top();
q.pop();
int u=fi.u;
if(fl[u]&&u!=st)
{
return dis[u];
} if(!vis[u])
{
vis[u]=;
for(int i=head[u];i;i=way[i].next)
{
int v=way[i].to;
int w=way[i].value;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
q.push((node){v,dis[v]});
}
}
}
}
return 0x3f3f3f3f;
}
int main()
{
int T;
cin>>T;
while(T--)
{
tot=;
memset(head,,sizeof(head));
fl.reset();
scanf("%d%d%d",&n,&m,&k);
for(int i=,u,v,w;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
for(int i=,u;i<=k;i++)
{
scanf("%d",&u);
fl[u]=;
}
long long ans=0x3f3f3f3f;
for(int i=;i<=n;i++)
{
if(fl[i])
{
ans=min(dijkstra(i),ans);
}
}
printf("%lld\n",ans);
}
return ;
}
最后的最后，不由得想吐槽一下，机房旁边的大佬（超链接）实在是太巨了，竟然还在搞什么
暴力碾标算，n^2过百万！！
数组开的大，不清也不怕！！