社区讨论

求助dalao。dijkstra为啥全RE,QwQ

P3371【模板】单源最短路径(弱化版)参与者 7已保存回复 14

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
14 条
当前快照
1 份
快照标识符
@mi6z41m8
此快照首次捕获于
2025/11/20 13:11
4 个月前
此快照最后确认于
2025/11/20 15:41
4 个月前
查看原帖
RT 代码如下。。本地过了,洛谷ide过了。。提交全部re
CPP
#include <iostream>
#include <queue>
#include <vector>
#define MAXN 500100
struct edge
{
    int to, len;
    edge(int _to, int _len)
    {
        to = _to;
        len = _len;
    };
    edge(){};
    bool operator<(const edge &e) const
    {
        return e.len < len;
    }
};
int N, M, S, dis[MAXN] = {0};
std::vector<edge> graph[MAXN];
void dijkstra()
{
    int vis[MAXN] = {0};
    std::priority_queue<edge> pq;
    dis[S] = 0;
    pq.push(edge(S, 0));
    while (!pq.empty())
    {
        edge head = pq.top();
        pq.pop();
        if (vis[head.to])
            continue;
        vis[head.to] = 1;
        for (int i = 0; i < graph[head.to].size(); i++)
        {
            edge now = graph[head.to][i];
            if (dis[now.to] > dis[head.to] + now.len)
            {
                dis[now.to] = dis[head.to] + now.len;
                now.len = dis[now.to];
                pq.push(edge(now.to, now.len));
            }
        }
    }
}
int main()
{
    std::cin >> N >> M >> S;
    for (int i = 0; i <= MAXN; i++)
    {
        dis[i] = 2147483647;
    }

    for (int i = 1; i <= M; i++)
    {
        int Fi, Gi, Wi;
        std::cin >> Fi >> Gi >> Wi;
        graph[Fi].push_back(edge(Gi, Wi));
    }
    dijkstra();
    for (int i = 1; i <= N; i++)
    {
        std::cout << dis[i] << " ";
    }
    return 0;
}

回复

14 条回复,欢迎继续交流。

正在加载回复...