不知道邻接矩阵存图对不对，题解好像都是邻接表存图qwq
by _____QWQ_____ @ 2023-12-17 14:07:58
不建议用矩阵存图
by R_aier @ 2023-12-17 14:24:21
@[______QAQ______](/user/1092781) 邻接矩阵没初值
by R_aier @ 2023-12-17 14:26:10
给个前向星板子：
```cpp
#define _edge(u) for(int i=head[u],v=e[i].v,w=e[i].w;i;i=e[i].ne,v=e[i].v,w=e[i].w)
struct edge{
int v,w,ne;
}e[maxn<<2];
int head[maxn],cnt;
void addedge(int u,int v,int w=1){
e[++cnt]={v,w,head[u]};
head[u]=cnt;
}
```
调用_edge(u)可以遍历u的所以出边
@[______QAQ______](/user/1092781)
by R_aier @ 2023-12-17 14:31:47
@[R_aier](/user/891245) emm...不用邻接表应该能过吧
by _____QWQ_____ @ 2023-12-17 14:38:56
@[R_aier](/user/891245) 我现在是想改改SPFA函数里的代码，能不能帮改改（已经改了半个多小时了qwq）
by _____QWQ_____ @ 2023-12-17 14:40:04
有重边
```cpp
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int n,m;
int a[1510][1510];
int d[1510];
bool f[1510];
void spfa()
{
for(int i=1;i<=n;i++) d[i]=-1e9;
queue<int> q;
q.push(1);
d[1]=0;
while(!q.empty())
{
int u=q.front();
for(int i=1;i<=n;i++)
{
if(d[u]+a[u][i]>d[i]&&a[u][i]!=0)
{
d[i]=d[u]+a[u][i];
if(!f[i])
{
f[i]=true;
q.push(i);
}
}
}
q.pop();
f[u]=false;
}
}
int main()
{
scanf("%d %d",&n,&m);
memset(a,-0x3f,sizeof(a));
for(int i=1;i<=m;i++)
{
int u,v,l;
scanf("%d %d %d",&u,&v,&l);
a[u][v]=max(a[u][v],l);////BUG
}
spfa();
if(d[n]!=-1e9) printf("%d",d[n]);
else printf("-1");
return 0;
}
```
@[______QAQ______](/user/1092781)
by R_aier @ 2023-12-17 14:50:44
@[______QAQ______](/user/1092781)
且用链式前向星更好，除非是folyd
by R_aier @ 2023-12-17 14:52:28
floyd试了，超时两个点
------------
（来自初一蒟蒻的提问：链式前向星是神么东西，听起来好厉害....qwq没学过）
by _____QWQ_____ @ 2023-12-17 14:57:27
@[R_aier](/user/891245)
by _____QWQ_____ @ 2023-12-17 14:58:37