~~没见过的SPFA写法增加了!~~
把栈换成队列
by _Remake_ @ 2022-11-11 23:37:28
@[_Remake_](/user/576702) 然而换成队列会T5个点，用栈只T了三个
by WEXI7111 @ 2022-11-11 23:40:23
@[WEXI7111](/user/767099) 你可以看一眼最新的提交记录
by _Remake_ @ 2022-11-11 23:48:39
我超 这是什么厌氧代码
by _Remake_ @ 2022-11-11 23:54:28
在较大的输入要求中，使用cin/cout时请关闭流同步
```
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int h[N],to[N],w[N],nxt[N],idx;
void add(int u,int v,int wt)
{
to[++idx]=v;w[idx]=wt;nxt[idx]=h[u];h[u]=idx;
return;
}
int dis[N],cnt[N];
bool inq[N];
int n,m;
bool spfa(int s)
{
stack<int>q;
dis[s]=0;q.push(s);inq[s]=1;
while(!q.empty())
{
int a=q.top();q.pop();
inq[a]=0;
for(int i=h[a];i!=-1;i=nxt[i])
{
int e=to[i];
if(dis[e]>dis[a]+w[i])
{
dis[e]=dis[a]+w[i];
cnt[e]=cnt[a]+1;
if(cnt[e]>n) return 1;
if(!inq[e]) {q.push(e);inq[e]=1;}
}
}
}
return 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
memset(h,-1,sizeof(h));
memset(dis,0x3f,sizeof(dis));
cin>>n>>m;
while(m--)
{
int tp,a,b,c;
cin>>tp>>a>>b;
if(tp==1) {cin>>c;add(a,b,-c);}
if(tp==2) {cin>>c;add(b,a,c);}
if(tp==3) add(a,b,0),add(b,a,0);
}
for(int i=1;i<=n;i++) add(0,i,0);
if(spfa(0)) cout<<"No";
else cout<<"Yes";
return 0;
}
```
215ms
by baoziwu2 @ 2022-11-11 23:58:01
@[_Remake_](/user/576702) 查询您未来程序完成度（
by baoziwu2 @ 2022-11-11 23:59:14
@[_Remake_](/user/576702) 破案了，开O2反向优化了，我之前交了一份queue的T了5个点，不开O2直接AC，太奇怪了
by WEXI7111 @ 2022-11-11 23:59:50
@[baoziwu2](/user/418670) 蚌了 #3不会公式 寄中寄
by _Remake_ @ 2022-11-12 00:01:24
@[_Remake_](/user/576702) #3不是自然数幂求和吗（
by baoziwu2 @ 2022-11-12 00:10:13
@[_Remake_](/user/576702) 直接进行一个度的白
by baoziwu2 @ 2022-11-12 00:11:53