Hello everyone, I was solving this Problem 20C - Dijkstra? and wrote a code and submitted but it gave me a TLE on test 28. Can I still improve my code's efficiency? I am not able to figure it out how to do so. Thanks.
My code
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Hello everyone, I was solving this Problem 20C - Dijkstra? and wrote a code and submitted but it gave me a TLE on test 28. Can I still improve my code's efficiency? I am not able to figure it out how to do so. Thanks.
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<int> vi;
#define inf 0x3f3f3f3f
vii *G;
vi D,P;
void Dijkstra(int s,int N){
D.assign(N+1,inf);
P.assign(N+1,-1);
D[s]=0;
P[s]=-1;
set<pii> Q;
Q.insert({s,0});
while(!Q.empty()){
auto top=Q.begin();
int u=top->first;
Q.erase(top);
if(u==N)return ;
for(auto next:G[u]){
int v=next.first,wt=next.second;
if(D[v]>D[u]+wt){
P[v]=u;
Q.erase({v,D[v]});
D[v]=D[u]+wt;
Q.insert({v,D[v]});
}
}
}
}
void print_shortest_path(int to){
vi path;
for(int i=to;i!=-1;i=P[i])path.push_back(i);
reverse(path.begin(),path.end());
for(auto i:path)cout<<i<<" ";
}
int main(){
int N,m;cin>>N>>m;
G= new vii[N+1];
for(int i=0;i<m;i++){
int a,b,w;cin>>a>>b>>w;
G[a].push_back({b,w});
G[b].push_back({a,w});
}
Dijkstra(1,N);
if(D[N]==inf)cout<<-1;
else
print_shortest_path(N);
//cout<<D[N]<<"\n";
}
Name |
---|
Use priority_queue (and don't erase old entries, just skip them later) instead of set for Q.
you can use priority_queue instead. std::set is too slow.
I have used priority_queue instead of std::set but I get CE in return. What should I do?
Priority queue can be a bit faster but using
set
and erasing elements is fine too, I always do it.Switch order in pair (vertex, dist) to (dist, vertex). Your current solution sorts by vertex id. This is quadratic or maybe even exponential. And don't forget about
long long
and biggerinf
because distances can get big.There is your code. But slightly modified.
I think your code has a bug (error).
I think your answer is not very helpful (useless).