蒟蒻88pts求调
查看原帖
蒟蒻88pts求调
488395
Proxima_Centauri楼主2023/6/18 11:58

被最后一个点hack了,求大佬帮助

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
int n, m, x1, yy1, x2, y2;
int dis[5][1510];
bool vis[1510];
int ans[1510];
int r[1510];
int g[1510][1510], f[1510][1510];
void spfa(int k, int s)
{
	queue<int> q;
	memset(vis, false, sizeof(vis));
	dis[k][s] = 0;
	vis[s] = true;
	q.push(s);
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		vis[x] = false;
		for (int i = 1; i <= n; i++)
			if (g[x][i])
				if (dis[k][i] > dis[k][x] + g[x][i])
				{
					dis[k][i] = dis[k][x] + g[x][i];
					if (vis[i]) continue;
					vis[i] = true;
					q.push(i);
				}
	}
}
int main()
{
	cin >> n >> m >> x1 >> yy1 >> x2 >> y2;
	for (int i = 1; i <= m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		g[u][v] = g[v][u] = w;
	}
	memset(dis, 0x3f, sizeof(dis));
	spfa(1, x1); spfa(2, yy1); spfa(3, x2); spfa(4, y2);
	memset(f, -0x3f, sizeof(f));
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			if (!g[i][j]) continue;
			if (dis[1][i] + g[i][j] + dis[2][j] == dis[1][yy1])
			{
				if (dis[3][i] + g[i][j] + dis[4][j] == dis[3][y2] || dis[4][i] + g[i][j] + dis[3][j] == dis[3][y2]) f[i][j] = g[i][j];
				else f[i][j] = 0;
				r[j]++;
			}
		}
	queue<int> q;
	q.push(x1);
	ans[x1] = 0;
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		for (int i = 1; i <= n; i++)
			if (f[x][i] >= 0)
			{
				r[i]--;
				ans[i] = max(ans[i], ans[x] + f[x][i]);
				if (r[i] == 0) q.push(i);
			}
	}
	cout << ans[yy1] << endl;
	return 0;
}
2023/6/18 11:58
加载中...