题目大意：
给出一个图和起点S，求补图中S到其他点的最短距离。
http://acm.hdu.edu.cn/showproblem.php?pid=5876
我自己的垃圾做法：
用线段树来维护dijkstra的dis数组。每次取出dis最小的点来更新其他点。 假设x连出去的边是y1 < y2 < y3 ... < yk. 那么对于dis[1, y1 - 1] [y1 + 1, y2 - 1] [y2 + 1, y3 - 1]...这些区间做区间取min操作。 比较容易出错的的地方是每次用x更新完其他点，需要把dis[x] 设置成INF， 对于一个区间，如果最小值就是INF，说明这个区间里的点都被扩展过了，直接return，而不能对它做取min操作。 因为需要做的取min操作是O(m)的，所以总的复杂度是O(mlogn).
简单做法：
用一个set维护哪些点还没被BFS到。 每次从队列取出一个点x， 然后把set里的点分成两类，一类是和x在原图中有边相连，一类是没有边相连，把和x没有边相连的点从set中删去，加入队列。 总的复杂度是O（mlogn）
参考代码：
//#pragma comment(linker, "/STACK:102400000,102400000")#include <bits/stdc++.h>
//zoj 3496
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
#define X first
#define Y second
#define MAXN 200020
#define M 105
const int mod = 1e9 + ;
const int INF = 1e9 + ; vector<int> E[MAXN];
int d[MAXN];
queue<int> Q;
set<int> st, tmp; void BFS(int S, int n)
{
Q.push(S); d[S] = ;
for (int i = ; i <= n; ++i)
if (i != S) st.insert(i);
while (!Q.empty())
{
int x = Q.front(); Q.pop();
tmp.erase(tmp.begin(), tmp.end());
for (auto y: E[x])
{
if (st.find(y) != st.end())
tmp.insert(y);
}
for (auto v: st) if (tmp.find(v) == tmp.end()) Q.push(v), d[v] = d[x] + ;
st = tmp;
}
bool flag = false;
for (int i = ; i <= n; ++i)
{
if (i == S) continue;
if (flag) printf(" ");
printf("%d", d[i]);
flag = true;
}
printf("\n");
} int main()
{
//freopen("input", "r", stdin);
//freopen("output", "w", stdout); int T, n, m;
scanf("%d", &T);
while (T--)
{
scanf("%d %d", &n, &m);
for (int i = ; i <= m; ++i)
{
int x, y;
scanf("%d %d", &x, &y);
E[x].push_back(y);
E[y].push_back(x);
}
int S;
scanf("%d", &S);
for (int i = ; i <= n; ++i) d[i] = -;
BFS(S, n);
for (int i = ; i <= n; ++i) E[i].clear();
} return ;
}