题目：这里
题意：
相当于一开始给一个初始好了的无向完全图给你，然后给让你删除m条边，再给你一个点v，最后问你在剩下的图里从这个点v出发能到达所有边点的最小路径是多少？
一看是所有点的最小路径，一看就觉得是个bfs，记忆化搜一下然后加个优化什么的，由于数据不知道是个什么奇葩而且比赛中还改数据，所以很多人wa的莫名其妙，
过也过的莫名其妙，我虽然过了但觉得有点不靠谱，赛后看了https://async.icpc-camp.org/d/546-2016的题解思路写了一发，总感觉更靠谱一点。
之前自己过的，就是用set记录那删掉的m条边，dis[i]数组记录每个结点的最小路径，当所有的点都搜到过的时候就可以结束了
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<set>
#include<queue>
using namespace std; const int M = 2e5 + ;
set<int>s[M];
int n;bool vis[M];
int dis[M],ans; int min(int x,int y){return x<y?x:y;} struct node{
int po,dis;
}; void bfs(int pos)
{
memset(vis,false,sizeof(vis));
queue<node>p;
node now,next;
now.po=pos;now.dis=;
p.push(now);
vis[pos]=true;
while (!p.empty()){
now=p.front();
p.pop();
for (int i= ; i<=n ; i++){
next.po=i;next.dis=now.dis+;
if (next.po==now.po) continue;
if (vis[next.po]) continue;
bool flag=false;
if (s[now.po].find(next.po)!=s[now.po].end())
flag=true;
if (flag) continue;
vis[next.po]=true;
dis[next.po]=min(next.dis,dis[next.po]);
p.push(next);ans++;
}
if (ans==n) return ;
}
} int main()
{
int t;
scanf("%d",&t);
while (t--){
int m;
scanf("%d%d",&n,&m);
for (int i= ; i<=n ; i++) s[i].clear(),dis[i]=M;
while (m--){
int u,v;
scanf("%d%d",&u,&v);
s[u].insert(v);
s[v].insert(u);
}
int pos;
scanf("%d",&pos);
ans=;
bfs(pos);
if (n!=pos){
for (int i= ; i<=n ; i++){
if (i==pos) continue;
if (i!=n) printf("%d ",dis[i]);
else printf("%d\n",dis[i]);
}
}
else{
for (int i= ; i<n ; i++){
if (i!=n-) printf("%d ",dis[i]);
else printf("%d\n",dis[i]);
}
}
}
return ;
}
后来看了别人的思路自己写的
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<set>
#include<queue>
using namespace std; const int M = 2e5 + ; int n,di[M],head[M],cas; struct Edge{
int to,next;
}edge[M*]; void add(int u,int v)
{
edge[++cas].next=head[u];
edge[cas].to=v;
head[u]=cas;
} int min(int x,int y){return x<y?x:y;} struct node{
int po,dis;
}; void bfs(int pos)
{
set<int>s,e;
set<int>::iterator it;
for (int i= ; i<=n ; i++) s.insert(i),di[i]=M;
queue<node>p;
s.erase(pos);
node now,next;
now.po=pos;now.dis=;
p.push(now);
while (!p.empty()){
now=p.front();
p.pop();
for (int i=head[now.po] ; i ; i=edge[i].next){
int v=edge[i].to;
if (s.find(v)==s.end()) continue;
s.erase(v);
e.insert(v);
}
for (it=s.begin() ; it!=s.end() ; it++){
next.po=*it;next.dis=now.dis+;
di[next.po]=min(next.dis,di[next.po]);
p.push(next);
}
s.swap(e);e.clear();
}
} int main()
{
int t;
scanf("%d",&t);
while (t--){
int m;cas=;
scanf("%d%d",&n,&m);
memset(head,,sizeof(head));
while (m--){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
int pos;
scanf("%d",&pos);
bfs(pos);
if (n!=pos){
for (int i= ; i<=n ; i++){
if (i==pos) continue;
if (i!=n) printf("%d ",di[i]);
else printf("%d\n",di[i]);
}
}
else{
for (int i= ; i<n ; i++){
if (i!=n-) printf("%d ",di[i]);
else printf("%d\n",di[i]);
}
}
}
return ;
}