Genkaim @ 2023-07-13 22:30:36
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
struct node{
ll next,w;
};
struct node2{
ll x,w;
};
vector<node> mp[N];
ll n,m,k,fx;
ll d[N];
bool vis[N];
bool operator > (node2 a, node2 b){
return a.w > b.w;
}
bool operator < (node2 a, node2 b){
return a.w < b.w;
}
priority_queue<node2, vector<node2> > q;
void f(ll sx){
memset(d, 0x7f, sizeof(d));
d[sx]=0;
q.push(node2{sx, 0});
while(!q.empty()){
node2 t = q.top();
ll x = t.x;
q.pop();//出队
if(vis[x])continue;
for(ll i = 0; i < mp[x].size(); ++i){
ll next = mp[x][i].next,w;
w = mp[x][i].w;
if(d[x]+w < d[next]){
d[next] = d[x]+w;
if(vis[next])continue;
q.push(node2{next, d[next]});
}
}
vis[x] = true;
}
}
int main(){
ll sx;
scanf("%d%d%d", &n, &m, &sx);
for(ll i = 1; i <= m; ++i){
ll x, y, w;
scanf("%d%d%d", &x, &y, &w);
mp[x].push_back(node{y, w});
}
f(sx);
for(ll i = 1; i <= n ;++i){
cout<<d[i]<<" ";
}
return 0;
}
蒟蒻问下为什么这代码会全RE啊
隔壁弱化版全过了 悲
顺带问下为什么堆优化less和greater互换隔壁弱化版都能过
by W_s_W @ 2023-07-13 23:18:07
@Genkaim 正如其名,堆优化只是优化,不会对正确性造成影响
你改了就相当于反向优化
by Genkaim @ 2023-07-14 07:15:58
@W_s_W 但是greater和less改了优先队列里面排序方式啊,这不是和dijkstra的原理冲突了吗 /_ \
by W_s_W @ 2023-07-14 08:14:37
@Genkaim 不用堆优化也是对的,用了堆优化只是先跑短路,你反过来就是先跑长路,但短路更短,也会跑
by Genkaim @ 2023-07-14 13:24:54
RE的问题解决了,scanf()忘改成ld了,但是还是只AC了一个点啊,求助大佬%%%%