cccccccc123 @ 2024-04-24 01:09:04
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <algorithm>
#include <unordered_map>
#include <numeric>
#include <utility>
#include <bitset>
using namespace std;
using ll = long long;
#define mp(i,j) make_pair(i, j)
inline int read() {
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int dis[maxn]; //记录距离
bool vis[maxn]; //标记是否入队
struct node {
int u; // 指向的节点
int w; // 权重
node (int a, int b) {
u = a;
w = b;
}
bool operator > (const node& a) const {return dis[u] > dis[a.u];}
};
std::vector<node> mp[maxn];
void solve() {
int n, m, s;
std::cin >> n >> m >> s;
for (int i = 1; i <= m; ++i) {
int u, v, w;
std::cin >> u >> v >> w;
mp[u].push_back(node{v, w});
}
priority_queue<node, vector<node>, greater<node>> q;
std::fill(vis, vis+maxn, 0);
std::fill(dis, dis+maxn, INF);
q.push(node(s, 0));
dis[s] = 0;
while (!q.empty()) {
auto tmp = q.top();
q.pop();
int u = tmp.u;
if (vis[u]) continue;
vis[u] = 1;
for (auto t : mp[u]) {
if (dis[t.u] > dis[u] + t.w) {
dis[t.u] = dis[u] + t.w;
q.push(node{t.u, t.w});
}
}
}
for (int i = 1; i <= n; ++i) {
std::cout << dis[i] << ' ';
}
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// std::cin >> t;
while (t--) {
solve();
}
}
应该是node运算符的问题,但是还过了4个点是怎么回事
by Reunite @ 2024-04-24 08:59:51
在执行
q.push(node{t.u, t.w});
的时候,要先判断是否已经在队列内。