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 PRabbitdad @ 2023-08-01 22:28:31

啊啊啊。

by wzb13958817049 @ 2023-08-01 22:29:26

@GRATRABBIT priority_queue要结构体

by wzb13958817049 @ 2023-08-01 22:29:55

@GRATRABBIT

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5,inf=214748364;
struct edge {
    int v, w;
};
struct node {
    int dis, u;
    bool operator>(const node& a) const { return dis > a.dis; }
};
vector<edge> e[maxn];
int dis[maxn], vis[maxn];
priority_queue<node, vector<node>, greater<node> > q;
void dijkstra(int n, int s) {
    memset(dis,0x3f3f3f3f, sizeof(dis));
    dis[s] = 0;
    q.push({0, s});
    while (!q.empty()) {
        int u = q.top().u;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i=0;i<e[u].size();i++) {
            int v = e[u][i].v, w = e[u][i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push({dis[v], v});
            }
        }
    }
}
int n,m,s;
int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(register int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        e[x].push_back({y,z});
    }
    dijkstra(n,s);
    for(register int i=1;i<=n;i++) printf("%d ",dis[i]);
    return 0;
} 

by wzb13958817049 @ 2023-08-01 22:30:26

@GRATRABBIT 就是说dis排序，然后还要存他的点

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

Thanks %%%