#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

#define MAXN 1100

const int NIL = INT_MAX ;
struct way
{
	int s;
	int d;
	bool operator <(const way k)const
	{
		return d < k.d;
	}
};

struct point//储存每个点的id和他最后的距离d
{
	int d,id;
	bool operator <(const point a)const
	{
		if(d == a.d)return id < a.id;
		return d > a.d;
	}
}p[MAXN];
	
int n,ans[MAXN];
int map[MAXN][MAXN];
bool flag[MAXN];

void dijk()//dijk求出每个点的最短路径
{
	priority_queue<way>Q;
	way temp,e;
	e.s = 2;
	e.d = 0;
	p[e.s].d = e.d;
    Q.push(e);
	while(!Q.empty())
	{
		e=Q.top();
		Q.pop();
		if(flag[e.s])continue;
		flag[e.s] = 1;
		for(int i = 1;i <= n; i++)
		{
			if(!flag[i] && map[e.s][i] != NIL && p[i].d > p[e.s].d + map[e.s][i] )
			{
				temp.s = i;
				temp.d = p[e.s].d + map[e.s][i];
				p[i].d = temp.d;
				Q.push(temp);
			}
		}
	}
}

void init(int m)//初始化
{
	int i,j;
	int a,b,c;
	for(i = 1; i <= n; ++i)
		{
			p[i].id = i;
			flag[i] = 0;
			p[i].d = NIL;
			ans[i] = 0;
			for(j = 1; j <= n; ++j)map[i][j] = NIL;
		}
	while(m--)
	{
		scanf("%d%d%d",&a,&b,&c);
		map[a][b] = c;
		map[b][a] = c;
	}
}

void dp()
{
	int i,j;
	for(i = 1; i <= n; ++i)if(p[i].id == 1)break;//先找出起点1
	ans[p[i].id] = 1;
	for(i; i < n; i++)
		for(j = i + 1; j <= n; j++)
			if(map[ p[j].id ][ p[i].id ] != NIL && p[j].d < p[i].d)//如果两个有边而且不等于则这条路径合法
				ans[ p[j].id ] += ans[ p[i].id ];
}

int main()
{
 // freopen("data.txt","r",stdin);
 
	int m;
	while(scanf("%d",&n))
	{
		if(n == 0)break;
		scanf("%d",&m);
		init(m);
		dijk();
		sort(p + 1,p + n + 1);//按照每个点从大到小的距离排序
		dp();
		printf("%d\n",ans[2]);//最后的答案就是终点ans[2]
	}
	return 0;
}

这是我的代码。。。有注释。应该不难看懂。希望大牛帮忙啊

• Re:附上代码。。能帮我看看吗 (55) DieIng 2008-08-17 13:26:25