题目描述

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 座城市之间两两最短路的最小值。

输入输出样例

输入 #1复制

输出 #1复制

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。

数据范围

测试点编号	nn 的规模	mm 的规模	约定
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(nlog²n),是来回跑两次Dijkstra，然后在染色什么的，还有一种要劣一点的就是按位是1还是0将其分为两堆，然后跑最短路，但我要说的是一个畜生算法，一个比BK201还要畜生的算法。

众所周知，Dijkstra就是一种贪心，在不停的放缩中求得最最优解，所以原题让我们求最小的，那我们可以一个一个去跑然后求得最小的，这很显然会T掉，但可以优化一下，每次跑完最小值后直接结束程序不就行了吗？

原题是让我们找最小距离，变化一下不就成了找最近的点吗？？？？Dijkstra的堆优化好像就有这样的性质，每次从堆顶取出一个元素，然后去跑，但堆顶的一定是最小的，所以当第一个出堆时，dis就已经确定，后面就不用跑了，自然万一图没有联通，最后就输出0x3f3f3f3f就可以了，

复杂度：

一下纯属玄学，可以直接跳过。

最快（暗指出题人不卡）O(m)的，但最坏，就会变成O（n²log 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过百万！！

数组开的大，不清也不怕！！

巴特西

洛谷 P 5 3 0 4 [GXOI/GZOI2019]旅行者