Pagini recente » Cod sursa (job #1845971) | Cod sursa (job #393698) | Cod sursa (job #2956672) | Cod sursa (job #1953214) | Cod sursa (job #654860)
Cod sursa(job #654860)
#include<fstream>
#include<vector>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int N,M,d[50001];
struct nod
{
int y,c;
};
vector<nod> V[50001];
queue<int> coada ;
void Read()
{
in >> N >> M;
int x;
nod t;
for(int i = 1; i <= M; i++)
{
in >> x >> t.y >> t.c;
V[x].push_back(t);
}
}
void Dijkstra()
{
int x,y,c,i;
for(i = 2; i <= N; i++)
d[i]=inf;
d[1]=0;
coada.push(1);
while(!coada.empty())
{
x=coada.front();
if(d[x]!=inf)
{
for(i = 0; i < V[x].size(); i++)
{
y = V[x][i].y;
c = V[x][i].c;
if(d[y] > d[x]+c)
{
d[y] = d[x]+c;
coada.push(y);
}
}
}
coada.pop();
}
}
int main()
{
Read();
Dijkstra();
for(int i = 2; i <= N; i++)
if(d[i]!=inf)
out<<d[i]<<" ";
else out<<"0";
}