0分求调

P4779 【模板】单源最短路径(标准版)

ZXmax2005 @ 2024-11-27 22:45:24

用的acwing的模板,0分求调试,本地能过样例

#include<bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;

int h[N], e[N], ne[N], idx;
int w[N];
int dist[N];
bool vistied[N];
int n, m;

void add(int a, int b, int c)
{
    w[idx] = c;
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({ 0,1 });

    while (heap.size())
    {
        PII k = heap.top();
        heap.pop();

        int ver = k.second, distance = k.first;

        if (vistied[ver]) continue;
        vistied[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({ dist[j],j });
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        cout << dist[i] << " ";
    }
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;

    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    dijkstra();

    return 0;
}

by szh_AK_all @ 2024-11-27 22:52:51

@ZXmax2005@ZXmax2005

输入的 s 呢?


by ZXmax2005 @ 2024-11-27 23:06:10

@szh_AK_all 是哦,看到数据说明s=1,默认从1开始了,忘记输入s了


by ZXmax2005 @ 2024-11-27 23:08:09

@szh_AK_all添加上s后,10分了,其他全部超时了


by szh_AK_all @ 2024-11-27 23:29:57

@ZXmax2005

把pii换成struct


by ZXmax2005 @ 2024-11-27 23:37:50

@szh_AK_all 改成这样还是超时

#include <bits/stdc++.h>

using namespace std;

struct Node
{
    int distance, vertex;

    bool operator<(const Node& other) const
    {
        return distance > other.distance;
    }
};

const int N = 1e5 + 10;

int h[N], e[N], ne[N], idx;
int w[N];
int dist[N];
bool visited[N];
int n, m, s;

void add(int a, int b, int c)
{
    w[idx] = c;
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;

    priority_queue<Node> heap;
    heap.push({ 0, s });

    while (!heap.empty())
    {
        Node k = heap.top();
        heap.pop();

        int ver = k.vertex, distance = k.distance;

        if (visited[ver]) continue;
        visited[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({ dist[j], j });
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
            cout << dist[i] << " ";
    }
    cout << endl;
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m >> s;

    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    dijkstra();

    return 0;
}

by Never_Gone @ 2024-11-29 09:03:54

你的e,ne,w用于存边的话边的范围应该是M=5e5+10

我用你的代码改成

#include <bits/stdc++.h>

using namespace std;

struct Node
{
    int distance, vertex;

    bool operator<(const Node& other) const
    {
        return distance > other.distance;
    }
};

const int N = 1e5 + 10;
const int M = 5e5 + 10;//这里

int h[N], e[M], ne[M], idx;
int w[M];
int dist[N];
bool visited[N];
int n, m, s;

void add(int a, int b, int c)
{
    w[idx] = c;
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;

    priority_queue<Node> heap;
    heap.push({ 0, s });

    while (!heap.empty())
    {
        Node k = heap.top();
        heap.pop();

        int ver = k.vertex, distance = k.distance;

        if (visited[ver]) continue;
        visited[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({ dist[j], j });
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
            cout << dist[i] << " ";
    }
    cout << endl;
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m >> s;

    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    dijkstra();

    return 0;
}

就可以过了


|