做这道题的时候，自己恰好刚看过dijstra算法。不过感觉有些地方还是不是那么好处理？去网上看了一下，大家好像说这个题很简单，就感觉自己太菜了。下面写下自己做这个题的过程。
首先，我要解决的是要存储消防站到火点的路径，并且是存储多个消防站到火点的路径，这个该怎么存储呢？此外，我要存储多个消防站到火点所用的时间，这个该怎么存储呢？还有，怎么根据输入消防站的个数不同来输出呢？这些都成为了我的困扰。
后来看了网上的代码，感觉对我帮助很大。
一、我用不用存储每个消防站到火点的路线呢？不用！！我只要将到达该点的最短路径的前驱存储就行了，用不着再用什么二维数组来存储消防站到火点的距离。举个例子，消防站标号为7，火点标号为2。我如何知道从消防站到火点的路径呢？就找7的前驱（假设为5），这个点就是消防站到火点的第一步，如果5的前驱不是2继续找5的前驱并继续下去，如果5的前驱是2了，那就结束。因此路径是7->5->2。
二、消防站到火点的时间怎么存储呢？我设置一个数组d[],d[i]就代表从火点到i的最短时间。
三、这个算法找到的是火点到各个路口的最短路径，但是我并不全要啊，我要的是那些消防站在的那些路口的数据。如何解决这个问题呢？我设置一个数组station[]，对那些消防站在的那些路口进行标记。比如，1号路口有消防站，则将station[1]标记为1，二号路口没有消防站，则将station[2]标记为0。最后根据station[i]是否为1来进行输出。
四、输出的时候要怎么处理呢？我如何保证对每个消防站都进行了输出呢？此时，我设置一个变量stasum记录消防站的个数，每输出一次，k++,当k!=stasum时，就保证输出结束了。
这些仅仅是一些方面，有什么问题的欢迎交流。。我是菜鸟。。
1 #include<iostream>
2 using namespace std;
3 #define MAXV 20
4 #define INF INT_MAX
5
6 int map[MAXV][MAXV],d[MAXV],parent[MAXV]; //d[i]表示是从火点到i点最短路径的长度
7 int n,fire,stasum,station[MAXV]; //parent[i]表示是在最短路径上i的前驱 fire表示的是火点所在的位置
8 //staion[i]的值用来标记消防站
9 void dijkstra(){
10 int i,j,v,tmp;
11 bool vis[MAXV];
12 memset(parent,-1,sizeof(parent));
13 memset(vis,false,sizeof(vis));
14 for(i=1;i<=n;i++) d[i]=INF;
15 d[fire]=0;
16
17 for(i=1;i<=n;i++){
18 tmp=INF;
19 for(j=1;j<=n;j++) //这个过程是找出离火点最近的并且是没有访问过的路口
20 if(d[j]<tmp && !vis[j]){
21 tmp=d[j];
22 v=j;
23 }
24 vis[v]=true;
25 for(j=1;j<=n;j++){
26 if(!vis[j] && map[v][j]!=-1 && d[j]>d[v]+map[v][j]){ //-1不能走
27 d[j]=d[v]+map[v][j];
28 parent[j]=v; //记录路径
29 }
30 }
31 }
32 }
33
34 void output(){
35 int j,i,tmp,v;
36 printf("Org Dest Time Path\n");
37
38 j=0;
39 while(j!=stasum){
40 tmp=INF;
41 for(i=1;i<=n;i++){ //每次找最小的时间输出
42 if(station[i] && d[i]<tmp){ //注意我是要找消防站点输出的啊，必须要求station[i]==1
43 tmp=d[i];
44 v=i;
45 }
46 }
47 station[v]=0; //将这个站点设为非消防站点（这点也很重要啊）
48 printf("%d %d %d",v,fire,d[v]);
49 while(v!=-1){
50 printf(" %d",v);
51 v=parent[v];
52 }
53 cout<<endl;
54 j++;
55 }
56 }
57
58 int main(){
59 int i,j,x;
60 scanf("%d",&n);
61 for(i=1;i<=n;i++){
62 for(j=1;j<=n;j++){
63 scanf("%d",&map[j][i]); //边反向存储
64 }
65 }
66 scanf("%d",&fire);
67 stasum=0;
68 memset(station,0,sizeof(station));
69 while(getchar()!='\n')
70 {
71 cin>>x;
72 station[x]=1; //标记消防站
73 stasum++; //计算消防站总数
74 }
75 dijkstra();
76 output();
77 return 0;
78 }