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 Wf_yjqd @ 2023-08-01 22:12:42

这题有说无环么，您不标记。

by Wf_yjqd @ 2023-08-01 22:12:54

@GRATRABBIT

by PRabbitdad @ 2023-08-01 22:13:44

emmm

by wzb13958817049 @ 2023-08-01 22:13:48

@Wf_yjqd 我记得没环吧

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

#include<bits/stdc++.h>
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];
bool vis[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();
        if(vis[now]) continue;
        vis[now] = 1;
        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:14:19

@Wf_yjqd 我dijkstra都能过

by FL_sleake @ 2023-08-01 22:14:35

试试scanf和printf

by PRabbitdad @ 2023-08-01 22:14:37

不T，WA

by PRabbitdad @ 2023-08-01 22:15:38

@tuohao 用不用好像无伤大雅？

by Wf_yjqd @ 2023-08-01 22:15:57

@wzb13958817049 您记得太对辣