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 | ecnerwala | 3648 |
2 | Benq | 3580 |
3 | orzdevinwang | 3570 |
4 | cnnfls_csy | 3569 |
5 | Geothermal | 3568 |
6 | tourist | 3565 |
7 | maroonrk | 3530 |
8 | Radewoosh | 3520 |
9 | Um_nik | 3481 |
10 | jiangly | 3467 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | adamant | 164 |
2 | awoo | 164 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 150 |
7 | SecondThread | 150 |
9 | orz | 146 |
10 | pajenegod | 145 |
Still Need to optimize my code for Dijkstra algo
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 |
---|