[模板]Dijkstra算法 WA 0

问题讨论区 提高段
1 
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<bool> vis;
vector<int> dis;
vector<vector<pair<int, int>>> edg;
int main()
{
    // freopen("dijkstras/uoj1.in", "r", stdin);
    // freopen("dijkstras/uoj1.out", "w", stdout);
    cin >> n >> m;
    priority_queue<pair<int, int>> pq;
    edg.resize(n + 1);
    dis.resize(n + 1, INT_MAX);
    vis.resize(n + 1, 0);
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        edg[u].push_back({w, v});
    }
    dis[1] = 0;
    pq.push({0, 1});
    while (!pq.empty())
    {
        auto hd = pq.top();
        pq.pop();
        if (vis[hd.second])
            continue;
        vis[hd.second] = 1;
        for (auto targ : edg[hd.second])
        {
            if (dis[targ.second] > dis[hd.second] + targ.first)
            {
                dis[targ.second] = dis[hd.second] + targ.first;
                if (!vis[targ.second])
                    pq.push({dis[targ.second], targ.second});
            }
        }
    }
    for (int i = 1; i <= n; i++)
        if (dis[i] == INT_MAX)
            cout << "inf" << " ";
        else
            cout << dis[i] << " ";
    // fclose(stdin);
    // fclose(stdout);
    return 0;
}
2

kanbudong

3

首先要开long long

4

还是寄

5

dijkstra里面for(auto ...)里面一定有问题

6

循环里面有问题

7

用小根堆！！！

8

用了

9

默认就是小根吧？（）

10

默认是大根！！

11

改成小根堆！！

12 
priority_queue<pair<int, int>，vector<pair<int,int> >,greater<pair<int,int> > > pq;
1 个赞
13

有朝一日还是败在了自己最熟悉的stl上啊！

image

14

给解决方案

15

给了

16

thank

17

@我命由我不由天 关帖吧