rt，SPFA 过了

这个优化以前应该就有，但数据一直没有加强

如果这个代码复杂度本来就是对的，当我没说

AC 代码：

#include <bits/stdc++.h>
using namespace std;
int n, m, s, dis[100010];
vector<int> v[100010], w[100010];
bool vis[100010];
struct cmp
{
	bool operator () (const int &x, const int &y)
	{
		return dis[x] > dis[y];
	}
};
void SPFA()
{
	priority_queue<int, vector<int>, cmp> q;
	q.push(s);
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	vis[s] = true;
	while (!q.empty())
	{
		int u = q.top();
		q.pop();
		vis[u] = false;
		for (int i = 0; i < v[u].size(); i++)
		{
			if (dis[v[u][i]] <= dis[u] + w[u][i]) continue;
			dis[v[u][i]] = dis[u] + w[u][i];
			if (vis[v[u][i]]) continue;
			q.push(v[u][i]);
			vis[v[u][i]] = true;
		}
	}
}
int main()
{
	cin >> n >> m >> s;
	while (m--)
	{
		int x, y, z;
		cin >> x >> y >> z;
		v[x].push_back(y);
		w[x].push_back(z);
	}
	SPFA();
	for (int i = 1; i <= n; i++) cout << dis[i] << " ";
	return 0;
}