spfa加优先队列不就是dijkstra吗。。
by zztqwq @ 2021-06-06 09:38:30
@[zzt_](/user/125913) 有一点小小的差别，就是vis[]这个数组还要清零，没啥大区别。同时spfa还要计数。都是些细枝末节的区别。毕竟想要直接访问有边的点并且不用邻接矩阵，也就剩个邻接表（就我所知的，我太菜了）。
不过为啥dfs spfa写tle了呢？
by 啷里个浪 @ 2021-06-06 17:03:27
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define aa 10010
int n,m,cnt,head[aa],dis[aa],vis[aa],sum[aa];
struct node{
int next,to,val;
}a[aa*4];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
void add(int u,int v,int w){
++cnt;
a[cnt].to =v;
a[cnt].val =w;
a[cnt].next =head[u];
head[u]=cnt;
}
bool spfa(int x){
vis[x]=1;
for(int i=head[x];i;i=a[i].next ){
int v=a[i].to ;
if(dis[v]>dis[x]+a[i].val ){
dis[v]=dis[x]+a[i].val ;
if(vis[v]||!spfa(v))return false;
}
}
vis[x]=0;
return true;
}
int main(){
//freopen("farm.in","r",stdin);
//freopen("farm.out","w",stdout);
n=read();m=read();
for(int i=1;i<=m;i++){
int flag=read();
if(flag==1){
int u,v,w;
u=read();v=read();w=read();
add(u,v,-w);
}else if(flag==2){
int u,v,w;
u=read();v=read();w=read();
add(v,u,w);
}else if(flag==3){
int u,v;
u=read();v=read();
add(u,v,0);
add(v,u,0);
}
}
int start=n+1;
for(int i=1;i<=n;i++)add(start,i,0);
memset(dis,0x3f,sizeof(dis));
dis[start]=0;
if(spfa(start))cout<<"Yes";
else cout<<"No";
return 0;
}
```
by 啷里个浪 @ 2021-06-06 17:04:25