记录编号	45394	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	青阳	是否通过	通过
代码语言	C	运行时间	0.005 s
提交时间	2012-10-23 19:04:59	内存使用	1.52 MiB

#include <stdio.h>
#define INF 0x7FFFFF
int map[100][100];
int path[100][101];
int dis[100];
int used[100];

#define QMAX 100
int queue[QMAX];
int head, rear;

void enqueue(int k)
{
	if(used[k]){
		return;
	}
	used[k] = 1;
	queue[rear] = k;
	rear = (rear + 1) % QMAX;
}

int exqueue(void)
{
	int k;
	k = queue[head];
	used[k] = 0;
	head = (head + 1) % QMAX;
	return k;
}

int main(void)
{
	int i, j;
	int m, n, s;
	int a, b, c;
	freopen("djs.in", "r", stdin);
	freopen("djs.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &s);
	for(i = 0; i < m; i++){
		scanf("%d%d%d", &a, &b, &c);
		map[a][b] = c;
	}
	for(i = 0; i < n; i++){
		dis[i] = INF;
	}
	dis[s] = 0;
	path[s][n] = 1;
	path[s][0] = s;
	enqueue(s);
	while(rear != head){
		c = exqueue();
		for(i = 0; i < n; i++){
			if(map[c][i] > 0 && dis[i] > dis[c] + map[c][i]){
				enqueue(i);
				for(j = 0; j < path[c][n]; j++){
					path[i][j] = path[c][j];
				}
				path[i][j] = i;
				path[i][n] = path[c][n] + 1;
				dis[i] = dis[c] + map[c][i];
			}
		}
	}
	for(i = 0; i < n; i++){
		printf("%d:\n", i);
		if(dis[i] == INF || i == s){
			printf("no\n");
		}else{
			printf("path:");
			for(j = 0; j < path[i][n]; j++){
				if(j != 0){
					printf(" ");
				}
				printf("%d", path[i][j]);
			}
			printf("\ncost:%d\n", dis[i]);
		}
	}
	return 0;
}