欢迎使用markdown
by 斗神·君莫笑 @ 2018-07-19 08:33:42
$dijkstra$复杂度是$O(n^2)$,要么加堆优化，要么用$SPFA$。QwQ
by disangan233 @ 2018-07-19 08:34:17
关键是你加了priority_queue的话就是要么这题卡STL，要么代码常数高了
by disangan233 @ 2018-07-19 08:35:30
@[disangan233](/space/show?uid=72679)
不存在呀，肯定他代码有问题
by Barry_Wang @ 2018-07-19 08:41:57
@[_barry·wang_](/space/show?uid=25004) 那我看看他代码
by disangan233 @ 2018-07-19 08:46:49
那个代码可以高亮一下吗？
by lixiao189 @ 2018-07-19 08:50:58
第一个问题,前向星是:
for(int i=head[x];i;i=next[i])
by disangan233 @ 2018-07-19 08:56:12
```cpp
#include<bits/stdc++.h>
#define N 500005
#define M 10001
#define MAX 2147483647
using namespace std;
int n,m,s,head[M],next[N],to[N],cnt,dis[M],l[N];
struct cmp{
bool operator() (int a,int b){
return dis[a]<dis[b];
}
};
priority_queue<int, vector<int>, cmp > que;
void add(int x,int y,int z){
next[++cnt]=head[x];
head[x]=cnt;
to[cnt]=y;
l[cnt]=z;
}
void search(){
int x;
while(!que.empty()){
x=que.top();
que.pop();
for(int i=head[x];to[i]!=0;i=next[i]){
if(dis[to[i]]>dis[x]+l[i]){
dis[to[i]]=dis[x]+l[i];
que.push(to[i]);
}
}
}
}
int main(){
int a,b,c;
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
for(int i=1;i<=n;i++)
dis[i]=MAX;
dis[s]=0;
que.push(s);
search();
for(int i=1;i<=n;i++)printf("%d ",dis[i]);
return 0;
}
```
by 打脸不疼 @ 2018-07-19 09:50:05
这样好看一些
第一次发见谅
by 打脸不疼 @ 2018-07-19 09:50:36
@[disangan233](/space/show?uid=72679) 改了，还是TLE
by 打脸不疼 @ 2018-07-19 09:58:17