Orz自己想出神仙正解的sxy
描述略
直接把所有起点推进去跑dijkstra...
并且染色，就是记录到这个点的最短路是由哪个起点引导出来的
然后再把所有边反指跑一次...
之后枚举每一条边两边的点不同色就可以更新答案
这个可能少有的代码比说得清楚...
#include<cstdio>
#include<queue>
#include<algorithm>
using std::min;
using std::priority_queue;
typedef long long lint;
,M=;
template<typename tp>inline void read(tp &kk)
{
tp ret=,f=;char ch=getchar();
;ch=getchar();}
+ch-';ch=getchar();}
kk=ret*f;
}
int n,m,k;
struct sumireko{int to,ne;lint v;}e[M];
int he[N],ecnt;
void addline(int f,int t,lint v)
{
if(f==t) return;
e[++ecnt].to=t;
e[ecnt].ne=he[f];
e[ecnt].v=v;
he[f]=ecnt;
}
int X[M],Y[M],l[N];lint V[M];
lint d[][N];][N];
struct shino{
lint di;int id;
shino(){}
shino(int ii,lint dd){id=ii,di=dd;}
bool friend operator < (shino a,shino b){return a.di>b.di;}
}g;
priority_queue<shino>q;
bool vv[N];
void dijkstra(lint *dis,int *c)
{
;i<=n;i++) dis[i]=0x3f3f3f3f3f3f3f3f;
;i<=k;i++) dis[l[i]]=,c[l[i]]=l[i],q.push(shino(l[i],));
while(!q.empty())
{
g=q.top();
q.pop();
int x=g.id;
vv[x]=;
for(int i=he[x],t;i;i=e[i].ne)
{
t=e[i].to;
if(vv[t]) continue;
if(dis[t]>dis[x]+e[i].v)
{
dis[t]=dis[x]+e[i].v;
c[t]=c[x];
q.push(shino(t,dis[t]));
}
}
}
}
;i<=n;i++) he[i]=,vv[i]=;ecnt=;}
int xi,yi,vi,T;
int main()
{
read(T);
while(T--)
{
read(n),read(m),read(k);
;i<=m;i++) read(X[i]),read(Y[i]),read(V[i]),addline(X[i],Y[i],V[i]);
;i<=k;i++) read(l[i]);
dijkstra(d[],fa[]);
clr();
;i<=m;i++) addline(Y[i],X[i],V[i]);
dijkstra(d[],fa[]);
lint ans=0x3f3f3f3f3f3f3f3f;
;i<=m;i++)
{
xi=X[i],yi=Y[i],vi=V[i];
][xi]&&fa[][yi]&&(fa[][xi]^fa[][yi]))
{
ans=min(ans,d[][xi]+vi+d[][yi]);
}
}
printf("%lld\n",ans);
clr();
}
;
}
哭唧唧