10pts,MLE求调
查看原帖
10pts,MLE求调
481621
Zhang_Wenjie楼主2023/10/1 10:46

rt

#include <bits/stdc++.h>
#define re register int
using namespace std;
typedef pair<int, int> pii;
const int N = 1e4 + 10, M = 2e5 + 10, inf = 0x3f3f3f3f;
struct edge
{
	int to, next;
}e[M];
int top, h[N];
int n, m, s, t, dist[N], out[N];
bool road[N], vis[N];
vector<int> g[N];
priority_queue< pii, vector<pii>, greater<pii> > q;

void add(int x, int y)
{
	e[++top] = (edge){y, h[x]};
	h[x] = top;
} 

void dfs(int x, int fa)
{
	if (x != t) out[x] --;
	road[x] = true;
	for (re i = 0; i < g[x].size(); i ++)
	{
		int y = g[x][i];
		dfs(y, x);
	}
}

void dijkstra()
{
	for (re i = 1; i <= n; i ++) dist[i] = inf;
	dist[s] = 0;
	q.push({0, s});
	while (!q.empty())
	{
		int x = q.top().second; q.pop();
//		cout << x << '\n';
		if (vis[x] || !road[x]) continue;
		vis[x] =true;
		for (re i = h[x]; i ; i = e[i].next)
		{
			int y = e[i].to, w = 1;
			if (road[y] && dist[x] + w < dist[y])
			{
				dist[y] = dist[x] + w;
//				cout << y << ' ' << dist[y] << '\n';
				q.push({dist[y], y});
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	for (re i = 1; i <= m; i ++)
	{
		int x, y;
		cin >> x >> y;
		add(x, y);
		g[y].push_back(x);
		out[x] ++;
	}
	cin >> s >> t;
	dfs(t, -1);
//	for (re i = 1; i <= n; i ++)
//		cout << i << ' ' << out[i] << '\n';
	for (re i = 1; i <= n; i ++)
		if (out[i]) road[i] = false;
//	for (re i = 1; i <= n; i ++)
//		cout << i << ' ' << road[i] << '\n';
	dijkstra();
	cout << (dist[t] == inf ? -1 : dist[t]) << '\n';
	
	return 0;
}
2023/10/1 10:46
加载中...