求调，悬一关

imsbNR @ 2024-07-10 22:07:19

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
unordered_map<ll, unordered_map<ll, ll>> dis;
vector<ll> G[N];
ll n, m, s, u, v, k, ans[N];
bool vis[N];
struct node
{
    ll to, v;
    friend bool operator < (node a, node b)
    {
        return a.v < b.v;
    }
};
priority_queue<node> q;
void dijkstra()
{
    memset(ans, 0x7f, sizeof ans);
    ans[s] = 0;
    q.push({s, 0});
    u = k = 0;
    while (!q.empty())
    {
        u = q.top().to;
        k = q.top().v;
        q.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (auto g : G[u])
        {
            if (ans[g] > ans[u] + dis[u][g])
            {
                ans[g] = ans[u] + dis[u][g];
                if (!vis[g])
                    q.push({g, ans[g]});
            }
        }
    }
    return;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v >> k;
        G[u].push_back(v);
        dis[u][v] = k;
    }
    dijkstra();
    for (int i = 1; i <= n; i++)
        cout << ans[i] << ' ';
    return 0;
}

by WilliamFranklin @ 2024-07-10 22:20:56

@imsbNR 不是存图的问题，dijkstra 函数中

            if (ans[g] > ans[u] + dis[u][g])
            {
                ans[g] = ans[u] + dis[u][g];
                if (!vis[g])
                    q.push({g, ans[g]});
            }

应该为

            if (ans[g] > ans[u] + dis[u][g])
            {
                ans[g] = ans[u] + dis[u][g];
                if (!vis[g])
                    q.push({ans[g], g}); // 这里有改动
            }

by imsbNR @ 2024-07-11 12:29:40

@WilliamFranklin 不是，我存的 node 先是是 g 在是 ans[g]

对了，我优先队列默认是大根堆，所以错了，现在改回来 48pt

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
unordered_map<ll, unordered_map<ll, ll>> dis;
vector<ll> G[N];
ll n, m, s, u, v, k, ans[N];
bool vis[N];
struct node
{
    ll to, v;
    friend bool operator < (node a, node b)
    {
        return a.v > b.v;
    }
};
priority_queue<node> q;
void dijkstra()
{
    memset(ans, 0x7f, sizeof ans);
    ans[s] = 0;
    q.push({s, 0});
    u = k = 0;
    while (!q.empty())
    {
        u = q.top().to;
        k = q.top().v;
        q.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (auto g : G[u])
        {
            if (ans[g] > ans[u] + dis[u][g])
            {
                ans[g] = ans[u] + dis[u][g];
                if (!vis[g])
                    q.push({g, ans[g]});
            }
        }
    }
    return;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v >> k;
        G[u].push_back(v);
        dis[u][v] = k;
    }
    dijkstra();
    for (int i = 1; i <= n; i++)
        cout << ans[i] << ' ';
    return 0;
}

继续求调

by WilliamFranklin @ 2024-07-11 14:22:46

@imsbNR 应该是你存图时边权有问题，如果又两条边都是从 u \rightarrow v，并且第二条的边权比第一条的大，但你 dis[u][v] 存的是第二条的边权，那么你此时就更劣了。

如果没口胡错的话，那代码：

    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v >> k;
        G[u].push_back(v);
        dis[u][v] = k;
    }

应改成

    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v >> k;
        G[u].push_back(v);
        if (!dis[u].count(v))
            dis[u][v] = k;
        else
            dis[u][v] = min(dis[u][v], k);
    }

by WilliamFranklin @ 2024-07-11 14:23:26

@imsbNR 你看看这样还有问题吗？

by WilliamFranklin @ 2024-07-11 14:24:02

我也不是很清楚还有哪里错了，应该就是这了吧。。。>~<

by imsbNR @ 2024-07-11 22:09:30

@WilliamFranklin 过了，谢谢你，泪目力，已关

by WilliamFranklin @ 2024-07-12 14:54:15

@imsbNR 呵呵，您也成为了我第 200 个，壶关！