Pagini recente » Cod sursa (job #1967510) | Cod sursa (job #1778669) | Cod sursa (job #1105257) | Cod sursa (job #448073) | Cod sursa (job #211893)
Cod sursa(job #211893)
#include <cstdio>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;
#define MAX_N 50001
#define n first
#define cost second
#define mp make_pair
#define pb push_back
vector <pair <int, int> > V[MAX_N];
queue <int> Q;
bitset <MAX_N> viz;
int N,M,D[MAX_N];
const int INF = 0x3f3f3f;
void citire()
{
int x,y,z;
scanf("%d %d",&N,&M);
for(int i = 1; i <= M; ++i)
{
scanf("%d %d %d",&x,&y,&z);
V[x].pb(mp(y,z));
}
}
void solve()
{
for(int i = 1; i <= N; ++i)
D[i] = INF;
Q.push(1);
viz[1] = true;
D[1] = 0;
while(!Q.empty())
{
int nod = Q.front();
Q.pop();
viz[nod] = false;
for(vector <pair <int, int> > :: iterator p = V[nod].begin(); p < V[nod].end(); p++)
if(D[p -> n] > D[nod] + p -> cost)
{
D[p -> n] = D[nod] + p -> cost;
if(viz[p -> n] == false)
{
Q.push(p -> n);
viz[p -> n] = true;
}
}
}
for(int i = 2; i <= N; ++i)
if(D[i] < INF)
printf("%d ",D[i]);
else
printf("0 ");
}
int main()
{
freopen("dijkstra.in","rt",stdin);
freopen("dijkstra.out","wt",stdout);
citire();
solve();
}