Practic

#include <fstream>

#include <vector>

#include <algorithm>

#include <queue>

using namespace std;

#define FILEIN "dijkstra.in"

#define FILEOUT "dijkstra.out"

const int MAXN = 50005;

const int INF = 0x3f3f3f3f;

int N, M;

vector< pair<int, int> > G[MAXN];

int Dmin[MAXN];

void ReadData() {

ifstream fin(FILEIN);

fin >> N >> M;

for (int i = 0; i < M; ++i) {

int a, b, c;

fin >> a >> b >> c;

G[a].push_back(make_pair(b, c));

}

}

void Solve() {

bool InQueue[MAXN];

queue<int> Q;

memset(Dmin, INF, sizeof(Dmin));

memset(InQueue, false, sizeof(InQueue));

Dmin[1] = 0;

Q.push(1);

InQueue[1] = true;

while (!Q.empty()) {

int nod = Q.front();

Q.pop();

InQueue[nod] = false;

for (vector< pair<int, int> >::iterator it = G[nod].begin(); it != G[nod].end(); ++it)

if (Dmin[nod] + it->second < Dmin[it->first]) {

Dmin[it->first] = Dmin[nod] + it->second;

if (!InQueue[it->first]) {

Q.push(it->first);

InQueue[it->first] = true;

}

}

}

}

void WriteData() {

ofstream fout(FILEOUT);

for (int i = 2; i <= N; ++i)

fout << (Dmin[i] < INF ? Dmin[i] : 0) << " ";

}

int main() {

ReadData();

Solve();

WriteData();

}