@[Tommyshizichen](/user/1124466) 菜就多练
by wywlsy @ 2024-03-02 10:38:43
@[Tommyshizichen](/user/1124466) 这道题好像卡$\text{SPFA}$？
by 42_TZY @ 2024-03-02 10:38:57
@[Tommyshizichen](/user/1124466)
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN=7e3+10;
int head[MAXN],nxt[MAXN<<1],to[MAXN<<1],wt[MAXN<<1],dist[MAXN],vis[MAXN],tot[MAXN],cnt=0,n,m;
void addedge(int u,int v,int w)
{
cnt++;
nxt[cnt]=head[u];
head[u]=cnt;
to[cnt]=v;
wt[cnt]=w;
}
int spfa()
{
memset(dist,0x3f,sizeof dist);
int u,v;
queue<int> q;
dist[0]=0;
vis[0]=1;
q.push(0);
while(!q.empty())
{
u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=nxt[i])
{
v=to[i];
if(dist[v]>dist[u]+wt[i])
{
dist[v]=dist[u]+wt[i];
if(!vis[v])
{
vis[v]=1;
tot[v]++;
if(tot[v]==n+1) return 0;
q.push(v);
}
}
}
}
return 1;
}
int main()
{
int u,v,w,opt;
cin>>n>>m;
for(int i=1;i<=n;i++) addedge(0,i,0);
for(int i=1;i<=m;i++)
{
cin>>opt>>u>>v;
if(opt==1)
{
cin>>w;
addedge(u,v,-w);
}
else if(opt==2)
{
cin>>w;
addedge(v,u,w);
}
else
{
addedge(u,v,0);
addedge(v,u,0);
}
}
if(spfa()) cout<<"Yes";
else cout<<"No";
return 0;
}
```
by wywlsy @ 2024-03-02 10:49:26
ac
by wywlsy @ 2024-03-02 10:50:32
@[wywlsy](/user/1182598) renji
by zhangshengzhe123 @ 2024-03-02 10:52:27
你TM人机 @[zhangshengzhe123](/user/1156321)
by wywlsy @ 2024-03-02 11:17:40
```
. wcnm
.
...
...
```
@[zhangshengzhe123](/user/1156321)
by wywlsy @ 2024-03-02 11:19:04