请求加强数据

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;
}