题意：
给出带权值的图，图上有一些特殊点，现在给出q个询问，对于每个询问，输出离该点最近的特殊点，如果有多个，则按升序输出。
思路：
因为有多次查询，不可能对于每个询问都去跑一遍最短路。必须以特殊点为起点跑一遍最短路，但是这样路径的记录就是问题了。正解是用bitset来记录状态，在最短路松弛更新状态时，继承前驱节点即可。1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 const int INF = 0x3f3f3f3f; 10 const int maxn = 10000+5; 11 12 int n,m,s,q,tot; 13 int head[maxn],d[maxn],a[1005]; 14 bool done[maxn],flag[maxn]; 15 bitset<1005> ans[maxn]; 16 int tmp[1005]; 17 18 struct node 19 { 20 int v,w,next; 21 }e[10*maxn]; 22 23 void addEdge(int u, int v, int w) 24 { 25 e[tot].v = v; 26 e[tot].w = w; 27 e[tot].next = head[u]; 28 head[u] = tot++; 29 } 30 31 struct HeapNode 32 { 33 int u,d; 34 HeapNode(int u, int d):u(u),d(d){} 35 bool operator< (const HeapNode& rhs) const 36 { 37 return d > rhs.d; 38 } 39 }; 40 41 42 void dijkstra(int st) 43 { 44 priority_queue Q; 45 for(int i=0;i<=n;i++) d[i] = INF; 46 d[st] = 0; 47 memset(done,0,sizeof(done)); 48 Q.push(HeapNode(st,0)); 49 while(!Q.empty()) 50 { 51 HeapNode x = Q.top(); Q.pop(); 52 int u = x.u; 53 if(done[u]) continue; 54 done[u] = true; 55 for(int i=head[u];i!=-1;i=e[i].next) 56 { 57 int v = e[i].v; 58 if(d[v] > d[u]+e[i].w) 59 { 60 d[v] = d[u] + e[i].w; 61 if(!flag[v]) ans[v] = ans[u]; //如果不是特殊点，就更新 62 Q.push(HeapNode(v,d[v])); 63 } 64 else if(d[v] == d[u]+e[i].w) ans[v]|=ans[u]; //相等的话，就加上当前点的答案 65 } 66 } 67 } 68 69 int main() 70 { 71 //freopen("in.txt","r",stdin); 72 while(~scanf("%d%d%d%d",&n,&m,&s,&q)) 73 { 74 tot = 0; 75 memset(head,-1,sizeof(head)); 76 memset(flag,0,sizeof(flag)); 77 for(int i=0;i<=n;i++) ans[i].reset(); 78 for(int i=1;i<=m;i++) 79 { 80 int u,v,w; 81 scanf("%d%d%d",&u,&v,&w); 82 addEdge(u,v,w); 83 addEdge(v,u,w); 84 } 85 for(int i=1;i<=s;i++) 86 { 87 scanf("%d",&a[i]); 88 addEdge(0,a[i],0); 89 flag[a[i]] = true; 90 ans[a[i]].set(i); //特殊点的答案就是自己 91 } 92 dijkstra(0); 93 while(q--) 94 { 95 int tot = 0; 96 int x;scanf("%d",&x); 97 for(int i=1;i<=s;i++) 98 if(ans[x].test(i)) tmp[tot++]=a[i]; 99 sort(tmp,tmp+tot);100 for(int i=0;i