社区讨论
求助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 条回复,欢迎继续交流。
正在加载回复...