堆优化版dijkstra算法求助
查看原帖
堆优化版dijkstra算法求助
408439
daozhang楼主2022/3/9 14:59

求大佬帮助orz,到底哪里不对啊 样例都过不了。

#include <iostream>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <climits>
#include <iomanip>
#include <bitset>
#define Buff std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll long long
#define inf LONG_LONG_MAX
#define Inf INT_MAX
#define MEM(x, y) memset(x, y, sizeof(x))
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define rrep(i, a, b) for (int i = (b); i >= (a); i--)
using namespace std;
const int MX = 1e7 + 10;
const ll Mod = 1e9 + 7;
const int INF = -0x3f3f3f3f;
const int N = 1e6 + 10;
int n, m, x;
int e[N], ne[N], h[N], w[N], dis[N], idx;
bool st[N];
typedef pair<int, int> PII;
void add(int a, int b, int c)
{
  e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dijkstra()
{
  memset(dis, 0x3f, sizeof dis);
  dis[x] = 0;
  priority_queue<PII, vector<PII>, greater<PII>> heap;
  heap.push({0, x});
  while (heap.size())
  {
    auto t = heap.top();
    heap.pop();
    int ver = t.second, distance = t.first;
    if (st[ver])
      continue;
    st[ver] = true;
    for (int i = h[ver]; i != -1; i = ne[i])
    {
      int j = e[i];
      if (dis[j] > dis[ver] + w[i])
      {
        dis[j] = dis[ver] + w[i];
        heap.push({dis[j], j});
      }
    }
  }
}
signed main()
{
  Buff;
  cin >> n >> m >> x;
  memset(h, -1, sizeof h);
  while (m--)
  {
    int a, b, c;
    cin >> a >> b >> c;
    add(a, b, c);
  }
  dijkstra();
  int ans = 0;
  for (int i = 1; i <= n; i++)
  {
    ans = max(ans, dis[i]);
  }
  cout << ans << endl;
  return 0;
}
2022/3/9 14:59
加载中...