# hdu 5876 Sparse Graph【最短路+思维】好题

2016-09-12

hdu 5876 Sparse Graph【最短路+思维】好题

# Sparse Graph

Time Limit: 4000/2000 MS (Java/Others)Memory Limit: 262144/262144 K (Java/Others)

Total Submission(s): 300Accepted Submission(s): 100

Problem Description
In graph theory, the complement of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G.

Now you are given an undirected graph G of N nodes and M bidirectional edges of unit length. Consider the complement of G, i.e., H. For a given vertex S on H, you are required to compute the shortest distances from S to all N?1 other vertices.

Input
There are multiple test cases. The first line of input is an integer T(1&le;T<35) denoting the number of test cases. For each test case, the first line contains two integers N(2&le;N&le;200000) and M(0&le;M&le;20000). The following M lines each contains two distinct integers u,v(1&le;u,v&le;N) denoting an edge. And S(1&le;S&le;N) is given on the last line.
Output
For each of T test cases, print a single line consisting of N?1 space separated integers, denoting shortest distances of the remaining N?1 vertices from S (if a vertex cannot be reached from S, output ``-1" (without quotes) instead) in ascending order of vertex number.
Sample Input
1 2 0 1
Sample Output
1

1、这算是出题事故了，一开始的时候说是M《=5500，那么问题其实就并不难了，如N大于了6000（大一点稍微稳妥一点），那么狠显然，无论这m条边如何建立的，其补图的从源点到其各个点的最短路要么是1，要么是2，因为很明显，如果m==0的时候，其源点到其他各个点都有一条值为1的最短路径直接相连，而且明显5500条边，当N大于5500的时候，是不可能将从源点到其各个点的最短路变成2以上的情况的（因为假设n==6000的时候，从源点到其他各个点的距离为2的走法一共有6000-2种，明显只去掉5500条边，是不能够使得某些最短距离变成3的）。。

2、那么当n<=6000的时候，直接按照其邻接矩阵跑其补图的最短路即可，否则如果n>6000那么按照输入的边，如果对应输入的无向边中有源点作为这条边的某个端点，那么规定其源点到这条边的另外一个端点的距离为2,即可。

Ac代码：

```#include
#include
#include
using namespace std;
int dis[300005];
int vis[20005];
int map[6005][6005];
int bian[10000][3];
int n,m,ss,cont;
void Dij()
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)dis[i]=0x3f3f3f3f;
dis[ss]=0;
for(int i=0;idis[j])
{
u=j;
tmp=dis[j];
}
}
vis[u]=1;
if(u==-1)continue;
for(int j=1;j<=n;j++)
{
int v=j;
int w=map[u][j];
if(w==0x3f3f3f3f)continue;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
}
}
}
for(int i=1;i<=n;i++)
{
if(dis[i]==0x3f3f3f3f)dis[i]=-1;
}
int f=0;
for(int i=1;i<=n;i++)
{
if(i==ss)continue;
if(f==0)printf("%d",dis[i]);
else printf(" %d",dis[i]);
f++;
}
printf("\n");
}
void Slove()
{
for(int i=0;i<6004;i++)
{
for(int j=0;j<6004;j++)
{
map[i][j]=1;
}
}
for(int i=0;i

```