2240879_wa.c

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>
# include <string.h>

int T, N;
int map[1001][1001];

void dijkstra()
{
	int i, j;
	int dis[1001];

	memset(dis,-1,sizeof(dis));
	dis[0] = 0;
	for(i = 0; i < N; i++)
	{
		for(j = 0; j < N; j++)
			if(dis[i]!=-1&&map[i][j]&&(dis[i]+map[i][j]<dis[j]||dis[j]==-1))
				dis[j] = map[i][j]+dis[i];
	}
	printf("%d\n",dis[N-1]);
}

void input()
{
	int i;
	int x, y, w;

	scanf("%d%d",&T,&N);
	memset(map,0,sizeof(map));
	for(i = 0; i < T; i++)
	{
		scanf("%d%d%d",&x,&y,&w);
		if(map[x-1][y-1]&&map[x-1][y-1]<w)
			continue;
		map[x-1][y-1] = map[y-1][x-1] = w;
	}
	dijkstra();
}

int main()
{
	input();
	return 1;
}