Cod sursa(job #1846170)

Utilizator radudurlesteanuDurlesteanu Radu Stefan radudurlesteanu Data 12 ianuarie 2017 11:57:29
Problema Algoritmul lui Dijkstra Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#define inf 1<<28
using namespace std;
int n,m,i,Dist[50005],x,d[50005],c;
struct node{
            int to,val;
           };
vector <node>G[50005];
void Read()
{
int m,x;
node p;
freopen("dijkstra.in","r",stdin);
scanf("%d%d",&n,&m);
while (m--)
    {
    scanf("%d%d%d",&x,&p.to,&p.val);
    G[x].push_back(p);
    d[x]++;
    }
}

void BellmanFord()
{
int x;
queue <int> Q;
Q.push(1);
for (int i=2;i<=n;i++) Dist[i]=inf;
Dist[1]=0;
while(Q.size()>0)
   {
    x=Q.front();Q.pop();
    for (int i=0;i<d[x];++i)
        {
        if (G[x][i].val+Dist[x]<Dist[G[x][i].to]) {
                                                   Dist[G[x][i].to]=G[x][i].val+Dist[x];
                                                   Q.push(G[x][i].to);
                                                  }
       }
   }
}

void Write()
{
freopen("dijkstra.out","w",stdout);
for(int i=2;i<=n;++i)
   {
    if (Dist[i]==inf) printf("0 ");
    else printf("%d ",Dist[i]);
   }
}
int main()
{
Read();
BellmanFord();
Write();
return 0;
}