题目如上。
暴力碾标算，n^2过百万！！
作为一道黑题它确实有点点水（如果是畜生解法的话）
就是找出两两点之间的最短路的最小值。
本来是很高深的一题，要跑两遍最短路啊，然后染色啊，再拓展什么的，但是！有一个大仙（不是bk201）暴力了一发。
解法：
考虑一个叫做dijkstra的算法（这里千万不能spfa），它是怎么跑的呢？
很简单，贪心找当前最短路，然后在利用下一个节点拓展下下一个节点。
然鹅，这个过程如果跑全图的话，会炸到M78星云去！！！
但是，由于奇妙的dijkstra的贪心正确性，我们拓展到的第一个节点就是当前最小值，于是，我们
退！出！
大爷我不跑了！
这波操作真的是非常神仙了！！！
通过这个可爱的return，我们省去了大量的时间和空间，有许多的点可以不用跑了！
（本质就是一个n^2暴力。。。）
神奇的是，这个dij的复杂度应该是和点数，标记点数反相关的，如果n-k的值越小，dij的速度越快，当然，如果n-k=0，那么这个dij基本就是线性，不，是O（1），甚至可以用一次扫描出边比最小值代替！
所以，它是一个伪n^2的算法。
（然后还是跟着zrx大佬学习了一种新的dijk打法。）
代码：
#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn=1e6+10; ll n,m,k; struct edge { ll to,next,dis; }e[maxn]; ll cnt,head[maxn]; inline void addedge(ll from,ll to,ll dis) { e[++cnt].next=head[from]; e[cnt].to=to; e[cnt].dis=dis; head[from]=cnt; } struct node//手动堆优化 { ll x; ll v; bool operator <(const node &an)const { return v>an.v; } }; ll dis[maxn]; bitset < maxn > vis,fl; ll dijkstra(int s) { priority_queue < node > q; vis.reset(); memset(dis,0x3f,sizeof(dis)); q.push((node){s,0}); dis[s]=0; while(!q.empty()) { node s1=q.top(); q.pop(); ll u=s1.x; if(fl[u]!=0&&u!=s)//第一个非起点标记点 return dis[u];//直接返回最小距离 if(vis[u]==0)//继续dij { vis[u]=1; for(ll i=head[u];i;i=e[i].next) { int v=e[i].to; if(dis[v]>dis[u]+e[i].dis) { dis[v]=dis[u]+e[i].dis; q.push((node){v,dis[v]}); } } } } return 0x3f3f3f3f3f3f3f3f; } int main() { int T; cin>>T; while(T--) { cnt=0; memset(head,0,sizeof(head)); fl.reset(); scanf("%lld%lld%lld",&n,&m,&k); for(ll i=1;i<=m;i++) { ll x,y,z; scanf("%lld%lld%lld",&x,&y,&z); addedge(x,y,z); } for(ll i=1;i<=k;i++) { ll x; scanf("%lld",&x); fl[x]=1; } ll ans=0x3f3f3f3f3f3f3f3f; for(ll i=1;i<=n;i++) { if(fl[i]!=0)//每个标记点都跑一遍 ans=min(dijkstra(i),ans); } printf("%lld ",ans); } return 0; }
下行有惊喜哦
膜拜下面这位大佬，有时间可以去他的博客水一水。
https://www.cnblogs.com/2529102757ab/
（完）