~~为什么我的spfa和你的不一样~~
by 圣地亚哥 @ 2018-07-06 15:27:21
@[圣地亚哥](/space/show?uid=87453) ~~大概是因为我是空手打的吧~~优化之后70分，还是WA了3个点
```
#include<iostream>
#include<cstdio>
#include<cstring>
#define INF 0x7ffffff
#define MAXN 800
using namespace std;
int dist[801],bj[801],n,m,cow,h[801],cnt=0,head=1,tail=1,q[801],pl[501];
struct gh{
int boy;
int next;
int door;
}a[3001];
void add(int x,int y,int c)
{
cnt++;
a[cnt].boy=y;
a[cnt].next=h[x];
a[cnt].door=c;
h[x]=cnt;
}
int SPFA(int s)
{
memset(bj,0,sizeof(bj));
for(int i=1;i<=n;i++)dist[i]=INF;dist[s]=0;
head=1,tail=1,q[head]=s;
do
{
int x=q[head];
head=(head+1)%MAXN;bj[x]=0;
for(int u=h[x];u;u=a[u].next)
if(dist[x]+a[u].door<dist[a[u].boy])
{
dist[a[u].boy]=dist[x]+a[u].door;
if(!bj[a[u].boy])
{
tail=(tail+1)%MAXN;
q[tail]=a[u].boy;
bj[a[u].boy]=1;
}
}
}
while(head!=tail);
int total=0;
for(int i=1;i<=cow;i++)total+=dist[pl[i]];
return total;
}
int main()
{
scanf("%d%d%d",&cow,&n,&m);
for(int i=1;i<=cow;i++)scanf("%d",&pl[i]);
for(int i=1,x,y,c;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&c);
add(x,y,c);
add(y,x,c);
}
int minn=INF;
for(int i=1;i<=n;i++)
minn=min(minn,SPFA(i));
printf("%d",minn);
}
```
by C201914 @ 2018-07-06 16:14:26