HDU2544用矩阵实现的Dijkstra

1#include <iostream>
2using namespace std;
3int road[105][105],dis[105],n;
4bool In[105];
5int Dijkstra(int start, int end);
6int main()
7{
8	int m,a,b,c;
9	while(cin>>n>>m && (n||m))
10	{
11		memset(road, 0, sizeof(road));
12		memset(In, 0, sizeof(In));
13		memset(dis, 0, sizeof(dis));
14		while(m--)
15		{
16			cin>>a>>b>>c;
17			if(road[a][b] == 0 || road[a][b] > c)
18			{
19				road[a][b] = c;	
20				road[b][a] = c;
21			}
22		}
23		cout<<Dijkstra(1,n)<<endl;
24	}
25}
26int Dijkstra(int start, int end)
27{
28	if(start == end)
29		return 0;
30	int min,i,temp;
31	In[start] = 1;
32	while(In[end] == 0)
33	{
34		min = 0x7FFFFFF;
35		for(i = 1; i <= n; i++)
36		{
37			if(In[i])continue;
38			if(road[start][i] && !dis[i])
39				dis[i] = road[start][i];
40			if(dis[i] && dis[i] < min)
41			{
42				temp = i;
43				min = dis[i];
44			}
45		}
46		if(min == 0x7FFFFFF)
47			break;
48		In[temp] = 1;
49		for(i = 1; i <= n; i++)
50			if(road[temp][i] && ! In[i])
51				if(!dis[i] || dis[i]>dis[temp]+road[temp][i])
52					dis[i] = dis[temp] + road[temp][i];
53	}
54	if(dis[end])
55		return dis[end];
56	else return -1;
57}