求调，全部输出0

Pursuewind @ 2023-06-02 21:23:53

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n, m, s;
int dis[N];
bool vis[N];
struct edge
{
    int to, w;
};
vector <edge> G[N];
struct node
{
    int dis, id;
    bool operator < (const node &a) const
    {
        return a.dis < dis;
    }
};
priority_queue <node> q;
void dij()
{
    q.push({0, s});
    for (int i = 1; i <= n; i ++) dis[i] = 2147483647;
    while (!q.empty())
    {
        node top = q.top();
        int now = top.id;
        int w = top.dis; 
        q.pop();
        if (vis[now]) continue;
        vis[now] = 1;
        for (int i = 0; i < G[now].size(); i ++)
        {
            int go = G[now][i].to;
            if (dis[go] > dis[now] + w)
            {
                dis[go] = dis[now] + w;
                if (!vis[go]) q.push({dis[go], go});
            }
        }
    }
}
int main()
{
    cin >> n >> m >> s;
    while (m --)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        G[u].push_back({v, w});
    }
    dij();
    for (int i = 1; i <= n; i ++) cout << dis[i] << " ";
    return 0;
}

by liangbowen @ 2023-06-02 21:28:08

你甚至没有使用到 G[i].w

by liangbowen @ 2023-06-02 21:29:19

然后初始化 dis[s]=0 即可。

by Tjqq @ 2023-06-02 21:29:31

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, s;
int dis[N];
bool vis[N];
struct edge
{
    int to, w;
};
vector <edge> G[N];
struct node
{
    int dis, id;
    bool operator < (const node &a) const
    {
        return a.dis < dis;
    }
};
priority_queue <node> q;
void dij()
{
    q.push({0, s});
    for (int i = 1; i <= n; i ++) dis[i] = 2147483647;
    dis[s]=0;
    while (!q.empty())
    {
        node top = q.top();
        int now = top.id;
        q.pop();
        if (vis[now]) continue;
        vis[now] = 1;
        for (int i = 0; i < G[now].size(); i ++)
        {
            int go = G[now][i].to,w=G[now][i].w;
            if (dis[go] > dis[now] + w)
            {
                dis[go] = dis[now] + w;
                if (!vis[go]) q.push({dis[go], go});
            }
        }
    }
}
int main()
{
    cin >> n >> m >> s;
    while (m --)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        G[u].push_back({v, w});
    }
    dij();
    for (int i = 1; i <= n; i ++) cout << dis[i] << " ";
    return 0;
}

错了三处，自己看吧

by Tjqq @ 2023-06-02 21:30:32

虽然我不是名歧er，但是你这个棕名还是挺耀眼的（

by Yun_Mengxi @ 2023-06-02 22:06:16

@Tjqq 主页最亮的星（

by Tjqq @ 2023-06-02 22:14:19

@Yun_Mengxi ^_^