今天北邮校赛的一道题，最短路。
一开始的思路是1000个点都做一次SPFA，然后找出到询问值的最短路，但是T到死。
后来想了一下，发现其实可以将1000个点都指向一个超级源点，然后由该点出发开始搜，只需一遍，最后输出结果就可以了。
今天在这题上浪费了太多的时间，发挥的不是很好=。=加油吧。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2005
#define inf 1<<28
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define FOR(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
using namespace std;
int head[10005];
struct kdq
{
int v,val,next;
}edge[1000005 * 2];
int num = 0;
int n , m;
void add(int s,int e,int val)
{
edge[num].v = s;
edge[num].val = val;
edge[num].next = head[e];
head[e] = num ++;
edge[num].v = e;
edge[num].val = val;
edge[num].next = head[s];
head[s] = num ++;
}
int dis[10005];
void init()
{
mem(head,-1);
for (int i = 0 ;i <= n ;i ++)
dis[i] = inf;
num = 0;
}
bool vis[10005];
int qu[10000005];
void spfa(int s)
{
int nn = 1, cn = 0;
qu[0] = s ;
vis[s] = 1;
dis[s] = 0;
while(nn > cn)
{
int temp = qu[cn ++];
vis[temp] = 0;
for (int i = head[temp] ;i != -1 ;i = edge[i].next)
{
int t = edge[i].v;
int tt = edge[i].val;
if(dis[t] > dis[temp] + tt)
{
dis[t] = dis[temp] + tt ;
if(!vis[t])
{
vis[t] = 1;
qu[nn ++] = t;
}
}
}
}
}
int main()
{
int T;
cin >> T;
while ( T -- )
{
cin >> n >> m ;
init();
for (int i = 0 ;i < m ;i ++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
int S ;
cin >> S ;
for(int i = 0 ; i < S ; i ++)//把起点全部和超级源点连起来，就是0.
{
int dd;
scanf("%d",&dd);
add(0,dd,0);
}
int E;
spfa(0);
cin >> E;
while( E -- )
{
int e;
cin >>e;
int ans = dis[e];
if(ans == inf)
ans = -1;
cout <<ans<<endl;
}
cout <<endl;
}
return 0;
}