SCU-4444 - Travel - 补图最短路

Donny

一个神奇的题目...

乍一看是个简单题,但是N达到了1e5,并且要分情况,其中一种情况要求补图的最短路。

赛时蛮力,结果不是WA就是T,不然就RE...

果然不得不用专业点的方法。

算是学到了一个新技能。

补图的关键是下面这个函数:

void bfs() {

queue<int> q;

for(int i=2;i<=n;i++) {

s.insert(i);

}

q.push(1);

dis[1]=0;

dis[n]=INF;

while(!q.empty()) {

int u=q.front();q.pop();

for(int i=0;i<edg[u].size();i++) {

int v=edg[u][i];

if(!s.count(v))continue;

s.erase(v);t.insert(v);

}

for(it = s.begin();it!=s.end();it++) {

q.push(*it);

dis[*it]=dis[u]+1;

}

s.swap(t);

t.clear();

}

printf("%lld\n",min(dis[n]*b,a));

}

其中s和t是两个set。

用这种方式可以快速遍历原图的补图。而且不需要重新构边。

VJ:

SCU-4444 - Travel

Github:

SCU-4444 - Github

By Donny
Last modified: 2017-08-27