SPFA极限卡常70分求助
查看原帖
SPFA极限卡常70分求助
249583
ClarisS117楼主2022/10/14 20:54

怎么调都上不了80,有个点就稍微超了几毫秒

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct Edge {
	int To, Weight;
};
int RebuildTime[205];
vector<Edge> Roads[205];


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	int n, m, q;

	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> RebuildTime[i];
		Roads[i+1].reserve(200);
	}

	for (int i = 0; i < m; i++)
	{
		int villageI, villageJ, length;
		cin >> villageI >> villageJ;
		cin >> length;
		Edge roadToI{}, roadToJ{};
		roadToI.Weight = roadToJ.Weight = length;
		roadToI.To = villageI, roadToJ.To = villageJ;
		Roads[villageI].push_back(roadToJ);
		Roads[villageJ].push_back(roadToI);
	}
	cin >> q;S
	for (int i = 0; i < q; i++)
	{
		int x, y, t;
		cin >> x >> y >> t;

		if (RebuildTime[x] > t || RebuildTime[y] > t)
		{
			cout << -1 << endl;
			continue;
		}
		queue<int> pendingQueue;
		int dis[205];
		for (int i = 0; i <= n; i++)
		{
			dis[i] = 1919810;
		}
		dis[x] = 0;
		for (Edge j : Roads[x])
		{
			if (RebuildTime[j.To] <= t)
			{
				pendingQueue.push(j.To);
				dis[j.To] = j.Weight;
			}
		}
		while (!pendingQueue.empty())
		{
			int currentFrom = pendingQueue.front();
			pendingQueue.pop();
			for (Edge to : Roads[currentFrom])
			{
				if (RebuildTime[to.To] <= t)
				if (dis[currentFrom] + to.Weight < dis[to.To])
				{
					pendingQueue.push(to.To);
					dis[to.To] = dis[currentFrom] + to.Weight;
				}
			}
		}
		if (dis[y] == 1919810)
			dis[y] = -1;
		cout << dis[y] << endl;
	}
	return 0;
}
2022/10/14 20:54
加载中...