_TLEer_的小号 @ 2022-07-20 08:59:18
rt.
手打了一遍,发现自己写的像优先队列优化的spfa.
所以这段到底是spfa还是dijkstra?
code在二楼。
by _TLEer_的小号 @ 2022-07-20 08:59:41
#include<bits/stdc++.h>
#define il inline
#define re register
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
struct ln{
int u,v,w,nxt;
}a[400010];
struct fk{
int a;
fk(int b){a=b;}
fk(){}
};
int dij[100010],lnsz,hd[100010],n,m,u,v,w,sor;
bool goed[100010];
void mrg(int u,int v,int w){
a[++lnsz].u=u;
a[lnsz].v=v;
a[lnsz].w=w;
a[lnsz].nxt=hd[u];
hd[u]=lnsz;
}
const bool operator< (const fk a,const fk b) {
return dij[a.a]>dij[b.a];
}
priority_queue<fk> q;
void dijkstra(int root){
q.push(fk(root));
dij[root]=0;
while(!q.empty()){
int tp=q.top().a;
q.pop();
goed[tp]=false;
for(int i=hd[tp];i;i=a[i].nxt)
if(dij[tp]+a[i].w<dij[a[i].v]){
dij[a[i].v]=dij[tp]+a[i].w;
if(!goed[a[i].v]){
q.push(fk(a[i].v));
goed[a[i].v]=true;
}
}
}
}
signed main(){
cin>>n>>m>>sor;
for(int i=0;i<m;i++){
cin>>u>>v>>w;
mrg(u,v,w);
}
for(int i=0;i<=n;i++)dij[i]=INF;
dijkstra(sor);
for(int i=1;i<=n;i++)
cout<<dij[i]<<' ';
cout<<endl;
return 0;
}
by Sharing666 @ 2022-07-20 09:02:46
感觉像优化的
by zesqwq @ 2022-07-20 09:03:43
@_TLEer_的小号 感觉是复杂度不正确的最差nmlogm 的SPFA
by _TLEer_的小号 @ 2022-07-20 09:04:57
@Sharing666 但是dijkstra的vis
(代码中的goed
)是不用重新赋值false
的吧(
by _TLEer_的小号 @ 2022-07-20 09:06:43
@zhouershan 那要怎么改成dijkstra啊(
by fjy666 @ 2022-07-20 09:09:10
SPFstra