上面的链接挂错了，实际是这个[链式前向星建图 55pts](https://www.luogu.com.cn/record/144726766)
by hzoi_Shadow @ 2024-01-28 07:08:22
你都不放代码我看什么。
题解里第一篇就是链式前向星写法，只能说大概你链式前向星写挂了。
by strcmp @ 2024-01-28 07:15:36
@[wql_cai](/user/551861)
```cpp
链式前向星
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
struct node
{
int nxt,to,w;
}e[30000];
int head[30000],vis[30000],dis[30000],num[30000],cnt=0,flag=0;
inline void add(int u,int v,int w)
{
cnt++;
e[cnt].nxt=head[u];
e[cnt].to=v;
e[cnt].w=w;
head[u]=cnt;
}
void spfa(int s)
{
vis[s]=1;
for(int i=head[s];i!=0;i=e[i].nxt)
{
if(dis[e[i].to]<dis[s]+e[i].w)
{
dis[e[i].to]=dis[s]+e[i].w;
if(vis[e[i].to]==1||flag==1)
{
flag=0;
cout<<"No"<<endl;
exit(0);
}
spfa(e[i].to);
}
}
vis[s]=0;
}
int main()
{
int n,m,i,u,v,w,pd;
scanf("%d%d",&n,&m);
memset(vis,0,sizeof(vis));
memset(dis,-0x3f,sizeof(dis));
for(i=1;i<=n;i++)
{
add(0,i,0);
}
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&pd,&u,&v);
if(pd==1||pd==2)
{
scanf("%d",&w);
}
if(pd==1)
{
add(v,u,w);
}
if(pd==2)
{
add(u,v,-w);
}
if(pd==3)
{
add(u,v,0);
add(v,u,0);
}
}
dis[0]=0x7f7f7f7f;
spfa(0);
if(flag==0)
{
cout<<"Yes"<<endl;
}
return 0;
}
```
```cpp
vector
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
vector<pair<int,int> >e[30000];
int vis[30000],dis[30000],num[30000],cnt=0;
bool spfa(int s)
{
vis[s]=1;
for(int i=0;i<e[s].size();i++)
{
if(dis[e[s][i].first]<dis[s]+e[s][i].second)
{
dis[e[s][i].first]=dis[s]+e[s][i].second;
if(vis[e[s][i].first]==1||spfa(e[s][i].first)==false)
{
return false;
}
}
}
vis[s]=0;
return true;
}
int main()
{
int n,m,i,u,v,w,pd;
cin>>n>>m;
memset(vis,0,sizeof(vis));
memset(dis,-0x3f,sizeof(dis));
for(i=1;i<=n;i++)
{
e[0].push_back(make_pair(i,0));
}
for(i=1;i<=m;i++)
{
cin>>pd>>u>>v;
if(pd==1||pd==2)
{
cin>>w;
}
if(pd==1)
{
e[v].push_back(make_pair(u,w));
}
if(pd==2)
{
e[u].push_back(make_pair(v,-w));
}
if(pd==3)
{
e[u].push_back(make_pair(v,0));
e[v].push_back(make_pair(u,0));
}
}
dis[0]=0x7f7f7f7f;
if(spfa(0)==true)
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
return 0;
}
```
by hzoi_Shadow @ 2024-01-28 07:35:58
同上，为什么链式前项星比vector慢这么多？
- 链式前项星
```cpp
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+10,P=1e9+7;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=1;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
int n,m,d[N];
int head[N],nxt[N],to[N],w[N],tot;
bool v[N];
void add(int x,int y,int z)
{
nxt[++tot]=head[x];
to[tot]=y;
w[tot]=z;
head[x]=tot;
}
bool spfa(int x)
{
v[x]=1;
for(int i=head[x];i!=-1;i=nxt[i])
{
int y=to[i],z=w[i];
if(d[y]>d[x]+z)
{
d[y]=d[x]+z;
if(v[y]||!spfa(y))
return 0;
}
}
v[x]=0;
return 1;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
read(n),read(m);
int s,x,y,z;
for(int i=0;i<=n;i++) head[i]=-1;
for(int i=1;i<=m;i++)
{
read(s);
if(s==1)
read(x),read(y),read(z),
add(x,y,~z+1);
else if(s==2)
read(x),read(y),read(z),
add(y,x,z);
else
read(x),read(y),
add(x,y,0),add(y,x,0);
}
for(int i=1;i<=n;i++) add(0,i,0);
memset(d,0x3f,sizeof(d));
d[0]=0;
cout<<(spfa(0)?"Yes":"No");
}
```
- vector
```cpp
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+10,P=1e9+7;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=1;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
int n,m,d[N];
bool v[N];
vector<pair<int,int>>e[N];
bool spfa(int x)
{
v[x]=1;
for(int i=0;i<e[x].size();i++)
{
int y=e[x][i].first,z=e[x][i].second;
if(d[y]>d[x]+z)
{
d[y]=d[x]+z;
if(v[y]||!spfa(y))
return 0;
}
}
v[x]=0;
return 1;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
read(n),read(m);
int s,x,y,z;
for(int i=1;i<=m;i++)
{
read(s);
if(s==1)
read(x),read(y),read(z),
e[x].push_back(make_pair(y,-z));
else if(s==2)
read(x),read(y),read(z),
e[y].push_back(make_pair(x,z));
else
read(x),read(y),
e[x].push_back(make_pair(y,0)),
e[y].push_back(make_pair(x,0));
}
for(int i=1;i<=n;i++) e[0].push_back(make_pair(i,0));
memset(d,0x3f,sizeof(d));
d[0]=0;
cout<<(spfa(0)?"Yes":"No");
}
```
vector AC了，链式前项星挂55TLE
by Charlie_ljk @ 2024-01-28 07:50:38
都是用 DFS 打的，但vector就没有被卡
by Charlie_ljk @ 2024-01-28 07:53:40
@[The_Shadow_Dragon](/user/848964) @[Charlie_ljk](/user/1055198)
遍历顺序的问题，可以把边打乱：
[R](https://www.luogu.com.cn/record/144728004)
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
struct node
{
int nxt,to,w;
}e[30000];
int head[30000],vis[30000],dis[30000],num[30000],cnt=0;
inline void add(int u,int v,int w)
{
cnt++;
e[cnt].nxt=head[u];
e[cnt].to=v;
e[cnt].w=w;
head[u]=cnt;
}
inline bool spfa(int s)
{
vis[s]=1;
for(int i=head[s];i!=0;i=e[i].nxt)
{
if(dis[e[i].to]<dis[s]+e[i].w)
{
dis[e[i].to]=dis[s]+e[i].w;
if(vis[e[i].to]==1||spfa(e[i].to)==false)
{
return false;
}
}
}
vis[s]=0;
return true;
}
int main()
{
int n,m,i,u,v,w,pd;
scanf("%d%d",&n,&m);
memset(vis,0,sizeof(vis));
memset(dis,-0x3f,sizeof(dis));
vector<tuple<int, int, int> > g;
for(i=1;i<=n;i++)
{
//add(0,i,0);
g.emplace_back(0, i, 0);
}
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&pd,&u,&v);
if(pd==1||pd==2)
{
scanf("%d",&w);
}
if(pd==1)
{
//add(v,u,w);
g.emplace_back(v, u, w);
}
if(pd==2)
{
//add(u,v,-w);
g.emplace_back(u, v, -w);
}
if(pd==3)
{
//add(u,v,0);
//add(v,u,0);
g.emplace_back(u, v, 0);
g.emplace_back(v, u, 0);
}
}
//mt19937 rd(chrono::system_clock::now().time_since_epoch().count());
//shuffle(g.begin(), g.end(), rd);
reverse(g.begin(), g.end());
for (auto & [u, v, w] : g) add(u, v, w);
dis[0]=0x7f7f7f7f;
if(spfa(0)==true)
{
printf("Yes\n");
}
else
{
printf("No\n");
}
return 0;
}
```
by 0x7f @ 2024-01-28 08:25:22
啊？
by Lixiang_is_potato @ 2024-01-28 09:03:46
你把vector连的点倒过来就T了
https://www.luogu.com.cn/record/144735417
具体原因是SPFA，遍历顺序不同，跑的次数应该也不同？？？？好像是这杨
by Trump_ @ 2024-01-28 09:30:55