Dijkstra为什么会TLE

PRabbitdad @ 2023-08-01 22:06:00

#include<bits/stdc++.h>
#define int long long
typedef long long ll;
const int MAXN = 1e5 + 5;
const int MAXT = 2e5 + 5;
const int MAXM = 3e5 + 5;
const int MOD = 998244353;
using namespace std; 
int dis[MAXN];
int n,m,s;
vector<pair<int,int> >G[MAXN];
void dijkstra(){
    for(int i=0;i<MAXN;i++) dis[i] = INT_MAX;
    priority_queue<int,vector<int>,greater<int> >q;
    dis[s] = 0;
    q.push(s);
    while(q.size()){
        int now = q.top();
        q.pop();
        for(int i=0;i<G[now].size();i++){
            int u = G[now][i].first;
            int d = G[now][i].second;
            if(dis[u] > dis[now] + d){
                dis[u] = dis[now] + d;
                q.push(u);
            }
        }
    }
    return;
}
signed main(){
    cin >> n >> m >> s; 
    for(int i=0;i<m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        G[u].push_back(make_pair(v,w));
        G[v].push_back(make_pair(u,w));
    }
    dijkstra();
    for(int i=1;i<=n;i++){
        cout << dis[i] << " ";
    }
    return 0;
}

by wzb13958817049 @ 2023-08-01 22:21:19

@Wf_yjqd 嗯呢

by Wf_yjqd @ 2023-08-01 22:21:20

写成广搜了。

by FL_sleake @ 2023-08-01 22:21:24

别忘了priority_queue从大到小排序的

by PRabbitdad @ 2023-08-01 22:21:31

int dis[MAXN];
int n,m,s;
vector<pair<int,int> >G[MAXN];
void dijkstra(){
    for(int i=0;i<MAXN;i++) dis[i] = INT_MAX;
    priority_queue<int,vector<int>,greater<int> >q;
    dis[s] = 0;
    q.push(s);
    while(q.size()){
        int now = q.top();
        q.pop();
        for(int i=0;i<G[now].size();i++){
            int u = G[now][i].first;
            int d = G[now][i].second;
            if(dis[u] > dis[now] + d){
                dis[u] = dis[now] + d;
                q.push(u);
            }
        }
    }
    return;
}

by PRabbitdad @ 2023-08-01 22:22:23

priority_queue<int,vector<int>,greater<int> >q;不是改升序了吗

by wzb13958817049 @ 2023-08-01 22:22:51

@tuohao

priority_queue<int,vector<int>,greater<int> >q;

就是从大到小

by FL_sleake @ 2023-08-01 22:23:21

按权值排序不是按点...

by wzb13958817049 @ 2023-08-01 22:23:28

@GRATRABBIT

 if(dis[u] > dis[now] + d){
                dis[u] = dis[now] + d;
                q.push(u);
            }

应该是这段的问题

by PRabbitdad @ 2023-08-01 22:23:39

emmm，Dijkstra不就是这么写么？？？我紫题都是这么过的啊。。。

by PRabbitdad @ 2023-08-01 22:24:04

今天刷道模板突然就废了？