试试
```cpp
priority_queue<pair<int, int> > q;
```
无优化的真心不会啊
我觉得优先队列优化好懂
by a2920353120 @ 2018-11-19 21:26:51
```cpp
priority_queue<pair<int , int> > q;
for(int i = 1; i <= n; i++) d[i] = INF;
d[St] = 0;
q.push(make_pair(0, St));
while(!q.empty()) {
int Now = q.top().second;
q.pop();
if(Vis[Now]) continue;
Vis[Now] = true;
for(int i = Head[Now]; i ; i = a[i].Nxt) {
int y = a[i].To, z = a[i].Dis;
if(d[y] > d[Now] + z) {
d[y] = d[Now] + z;
q.push(make_pair(-d[y], y));
}
}
}
```
by a2920353120 @ 2018-11-19 21:29:02
@[wqiaoccc](/space/show?uid=138328) inf+inf爆了int,导致变成负的
by uwagjaynoi @ 2018-11-19 21:54:29
说真的建议学一学堆优化Dijkstra
再说这数据范围$\Theta(n^2)$也过不了啊 @[wqiaoccc](/space/show?uid=138328)
by _LiM @ 2018-11-19 22:09:36
忘了回了。
感谢大佬指点,确实是数据越界了,要过的话dis数组需要long long,@[Goblinmagupta](/space/show?uid=77144)
这个题Θ(n2)是能过的@[LiM_817](/space/show?uid=56724)
不过优先队列确实好用hhhhhhhh..
by wqiaoccc @ 2018-11-21 20:08:24