卑微蒟蒻在线求解

P4779 【模板】单源最短路径(标准版)

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了一个点啊,求助大佬%%%%


|