Pagini recente » Cod sursa (job #2691440) | Cod sursa (job #2420089) | Cod sursa (job #898083) | Cod sursa (job #2076742) | Cod sursa (job #2424549)
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int NMAX=100002;
const int MMAX=250002;
const int INF=0x3f3f3f3f;
vector <pair <int,int> > G[NMAX]; //lista adiacenta
priority_queue <pair <int,int> > pq;
int dist[NMAX];
int viz[NMAX];
int main(){
freopen("dijkstra2.in","r",stdin);
freopen("dijkstra2.out","w",stdout);
int n,m,src;
int u,v,c;
scanf("%d%d%d",&n,&m,&src);
for(int i=1;i<=m;++i){
scanf("%d%d%d",&u,&v,&c);
G[u].push_back({v,c});
G[v].push_back({u,c});
}
//init dist
for(int i=1;i<=n;++i)
dist[i]=INF;
dist[src]=0;
//
//for(int i=1;i<=n;++i)
// pq.push({-dist[i],i});
pq.push({0,src});
while(!pq.empty()){
pair <int,int> best=pq.top();
pq.pop();
u=best.second;
if(viz[u])
continue;
viz[u]=1;
for(int i=0;i<G[u].size();++i){
v=G[u][i].first;
c=G[u][i].second;
if(dist[v]>dist[u]+c){
dist[v]=dist[u]+c;
pq.push({-dist[v],v});
}
}
}
for(int i=1;i<=n;++i){
if(dist[i]==INF)
dist[i]=-1;
printf("%d ",dist[i]);
}
return 0;
}