本题初次放弃于2024.9.3 16:05，今天浏览题单时发现该遗留问题，决定再次挑战

错误代码：

#include<stdio.h>
#include<stdlib.h>
#define MIN -225555555
typedef struct
{
	int connect, dist;
}node;
node graph[1502][1502];
int indegree[1502];
int visit[1502];
int visit2[1502];
int maxdistance[1502];
int Max(int a, int b) { return a > b ? a : b; }
void dfs(int current, int p)
{
	visit2[current] = 1;
	for (int i = 1; i <= p; i++)
		if (graph[current][i].connect != 0 && !visit2[i])
			dfs(i, p);
}
void vanish(int p, int current)
{
	visit[current] == 1;
	for (int j = current + 1; j <= p; j++)
		if (graph[current][j].connect != 0 && !visit[j])
		{
			--indegree[j];
			if (indegree[j] == 0) vanish(p, j);
		}
}
void toposort(int p)
{
	int queue[1502], front = 0, back = 0;
	queue[front++] = 1;
	visit[1] = 1;// 存入起点1
	for (int i = 2; i <= p; i++)// 找到除1外所有入度为0的点，并递归删除他们的影响
	{
		if (indegree[i] == 0)
			vanish(p, i);
	}
	while (front > back)// 拓扑排序本体
	{
		int temp = queue[back++];
		visit[temp] = 1;
		for (int i = temp + 1; i <= p; i++)
		{
			if (graph[temp][i].connect != 0 && !visit[i])
			{
				--indegree[i];
				maxdistance[i] = Max(maxdistance[i], maxdistance[temp] + graph[temp][i].dist);
				if (!indegree[i]) queue[front++] = i;
			}
		}
	}
}
int main()
{
	int p, v, p1, p2, lon;
	scanf("%d%d", &p, &v);
	for (int i = 2; i <= p; i++)
		maxdistance[i] = MIN;
	for (int i = 0; i < v; i++)
	{
		scanf("%d%d%d", &p1, &p2, &lon);
		graph[p1][p2].connect = 1;
		graph[p1][p2].dist = lon;
		++indegree[p2];
	}
	dfs(1, p);
	if (!visit2[p])
	{
		printf("-1");
		return 0;
	}
	toposort(p);
	printf("%d", maxdistance[p]);
	return 0;
}
/* 
    maybe oneday I'll be back
                   ————2024.9.3 16:05
*/

新代码（负边邻接矩阵+spfa）

#include<stdio.h>
#include<stdlib.h>
#define MAX 0x3f3f3f3f
int p, v, g[1502][1502], visit[1502], queue[150000], dis[1502];
void spfa()
{
	for (int i = 1; i <= p; ++i) dis[i] = MAX;
	int front = 0, back = 0;
	dis[1] = 0;
	queue[front++] = 1;
	visit[1] = 1;
	while (back < front)
	{
		int t = queue[back++];
		visit[t] = 0;
		for (int i = 1; i <= p; ++i)
			if (g[t][i] != MAX && dis[i] > dis[t] + g[t][i])
			{
				dis[i] = dis[t] + g[t][i];
				if (!visit[i])
				{
					queue[front++] = i;
					visit[i] = 1;
				}
			}
	}
}
int main()
{
	int p1, p2, w;
	scanf("%d%d", &p, &v);
	for (int i = 1; i <= p; ++i)
		for (int j = 1; j <= p; ++j)
			g[i][j] = MAX;// 初始化邻接矩阵
	for (int i = 0; i < v; ++i)
	{
		scanf("%d%d%d", &p1, &p2, &w);
		g[p1][p2] = -w;
	}// 读入邻接矩阵，将权重取反，转化为spfa求最短路
	spfa();
	if (dis[p] == MAX) printf("-1");
	else printf("%d", -dis[p]);
	return 0;
}

到底为什么，都是我的错

决定转用链式前向星

但是先吃个饭

我还是决定不吃饭了

————————————————————————————————————

十分钟后：过辣！

#include<stdio.h>
#include<stdlib.h>
#define MAX 0x3f3f3f3f
typedef struct
{
	int to, next, w;
}edge;
edge e[50002];
int p, v, head[1502], visit[1502], queue[150000], dis[1502], cnt = 0;
void add(int p1, int p2, int w)
{
	e[cnt].to = p2;
	e[cnt].w = w;
	e[cnt].next = head[p1];
	head[p1] = cnt++;
}
void spfa()
{
	for (int i = 1; i <= p; ++i) dis[i] = MAX;
	int front = 0, back = 0;
	dis[1] = 0;
	queue[front++] = 1;
	visit[1] = 1;
	while (back < front)
	{
		int t = queue[back++];
		visit[t] = 0;
		for (int i = head[t]; i != -1; i = e[i].next)
		{
			int to = e[i].to, w = e[i].w;
			if (dis[to] > dis[t] + w)
			{
				dis[to] = dis[t] + w;
				if (!visit[to])
				{
					queue[front++] = to;
					visit[to] = 1;
				}
			}
		}
	}
}
int main()
{
	int p1, p2, w;
	scanf("%d%d", &p, &v);
	for (int i = 0; i <= p; ++i) head[i] = -1;
	for (int i = 0; i < v; ++i)
	{
		scanf("%d%d%d", &p1, &p2, &w);
		add(p1, p2, -w);
	}// 读入邻接表，将权重取反，转化为spfa求最短路
	spfa();
	if (dis[p] == MAX) printf("-1");
	else printf("%d", -dis[p]);
	return 0;
}

我爱链式前向星

蓟县。