qvq
by Loi_Anina @ 2018-10-14 09:05:41
by Candice_ @ 2018-10-14 09:07:17
就只有这里用了vis数组QAQ
by Candice_ @ 2018-10-14 09:09:07
@[Candice_](/space/show?uid=118209) 我的堆优化dij都不用vis数组的（逃
by 曹老师 @ 2018-10-14 09:09:45
@[曹老师](/space/show?uid=37427) 我问的同学们qaq也不加qaq所以我才会发讨论啊啊啊啊啊QAQ
还是谢谢你qwq
by Candice_ @ 2018-10-14 09:10:46
不加vis是假的dij啊， O((n+m)log(n))的
by LPA20020220 @ 2018-10-14 09:15:12
@[曹老师](/space/show?uid=37427)
by LPA20020220 @ 2018-10-14 09:15:27
```cpp
void dj()
{
std::memset(dis, 63, sizeof(dis));
q.push({st, 0}), dis[st] = 0;
Pass cur; R int now, i;
W (!q.empty())
{
cur = q.top(); q.pop(); now = cur.pos;
for (i = head[now]; i; i = edge[i].nex)
{
if(dis[edge[i].to] > dis[now] + edge[i].len)
{
dis[edge[i].to] = dis[now] + edge[i].len;
if(!vis[edge[i].to])
hdle[edge[i].to] = q.push({edge[i].to, dis[edge[i].to]}), vis[edge[i].to] = true;
else
{q.modify(hdle[edge[i].to], {edge[i].to, dis[now] + edge[i].len});}
}
}
}
}
```
by LPA20020220 @ 2018-10-14 09:16:22
@[LPA20020220](/space/show?uid=67492) emm所以为什么不初始
vis[起点] = 1呢QAQ
by Candice_ @ 2018-10-14 09:20:44
@[LPA20020220](/space/show?uid=67492) 哦我明白了QAQ谢谢您qwq
by Candice_ @ 2018-10-14 09:21:28