记录编号	23774	评测结果	AWWWWAWWW
题目名称	工程规划	最终得分	22
用户昵称	苏轼	是否通过	未通过
代码语言	C++	运行时间	0.290 s
提交时间	2011-03-20 12:53:43	内存使用	2.91 MiB

#include <fstream>
#include <cstdlib>
#include <cstring>
#include <queue>

using namespace std;

typedef struct LIST_NODE {
	int end, t;
	LIST_NODE *next;
} *GLIST;

int N, M, ct;
GLIST *lk;
ifstream fin("work.in");
ofstream fout("work.out");

inline void addway (const short a, const short b, const short t)
{
	LIST_NODE *newnode = (LIST_NODE*)malloc(sizeof(LIST_NODE));
	newnode->end = b;
	newnode->t = t;
	newnode->next = lk[a];
	lk[a] = newnode;
}


void spfa (const int wh)
{
	queue<int> q;
	int dist[N];
	bool boo[N];
	memset(dist, 0x2F, sizeof(dist));
	memset(boo, 0, sizeof(boo));

	boo[wh] = true;
	dist[wh] = 0;
	q.push(wh);
	while (!q.empty())
	{
		int curr = q.front();
		q.pop();

		for (LIST_NODE *pi=lk[curr]; pi; pi=pi->next)
		{
			ct++;
			if (dist[curr] + pi->t < dist[pi->end])
			{
				dist[pi->end] = dist[curr] + pi->t;

				if (!boo[pi->end])
					q.push(pi->end);
			}
		}

		boo[curr] = false;
		if (ct > 7000000)
		{
			fout << "NO SOLUTION" << endl;
			return;
		}
	}

	int stime = dist[0];
	for (int i=1; i<N; i++)
		if (dist[i] < stime)
			stime = dist[i];

	for (int i=0; i<N; i++)
		fout << dist[i]-stime << endl;
}

int main()
{
	fin >> N >> M;

	lk = (GLIST*)malloc(N*sizeof(GLIST));
	memset(lk, 0, N*sizeof(GLIST));

	int deg[N];
	memset(deg, 0, sizeof(deg));
	for (int i=0; i<M; i++)
	{
		int I, J, B;
		fin >> I >> J >> B;
		addway(J-1, I-1, B);
		deg[I-1]++;
	}

	int mindeg = deg[0], k = 0;
	for (int i=1; i<N; i++)
		if (deg[i] < mindeg)
			mindeg = deg[i],
			k = i;
			
	spfa(k);

	fin.close();
	fout.close();

	return 0;
}