1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| #include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int edge[1005][1005];
int maxint=1000001;
int vis[1005];//是否访问过
int dist[1005];//源点到i点的最短路径
int path[1005];
int n,m;
void dijstra(int s)
{
//init
for(int i=1;i<=n;i++){
vis[i]=0;
dist[i]=edge[s][i];
}
vis[s]=1;
//使所有的点都访问过，在vis[]内标记为1
for(int i=1;i<n;i++){
int Min=maxint;
int tmp=0;
//找出最小dist[j]
for(int j=1;j<=n;j++){
if(Min>dist[j]&&!vis[j]){
Min=dist[j];
tmp=j;
}
}
vis[tmp]=1;
for(int j=1;j<=n;j++){
if(edge[tmp][j]!=maxint&&!vis[j]){
//存在边
//试图更新
int d=Min+edge[tmp][j];
if(d<dist[j]){
dist[j]=d;
}
}
}
}
//for(int i=1;i<=n;i++)cout<<dist[i]<<" ";cout<<endl;
}
int DFS(int x)
{
//遇到算过的路径
if(path[x]!=-1){
return path[x];
}
//遇到结尾2,1条路径
if(x==2){return 1;}
path[x]=0;
for(int i=1;i<=n;i++){
if(edge[x][i]!=maxint&&dist[i]<dist[x]){
path[x]+=DFS(i);
}
}
return path[x];
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
if(!n)break;
scanf("%d",&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
edge[i][j]=maxint;
}
}
int x,y,d;
for(int i=0;i<m;i++){
scanf("%d %d %d",&x,&y,&d);
edge[x][y]=d;
edge[y][x]=d;//无向图
}
dijstra(2);
dist[2]=0;//少了这一步的话，
//dist[2]为maxint，很大
//不能满足dist[i]<dist[x]条件
memset(path,-1,sizeof(path));
cout<<DFS(1)<<endl;
//for(int i=1;i<=n;i++)cout<<path[i]<<" ";
}
return 0;
}
|