L2-001 紧急救援 （25 分)
作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。

输入格式:
输入第一行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0 ~ (N−1)；M是快速道路的条数；S是出发地的城市编号；D是目的地的城市编号。

第二行给出N个正整数，其中第i个数是第i个城市的救援队的数目，数字间以空格分隔。随后的M行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。

输出格式:
第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。

输入样例:
4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2
输出样例:
2 60
0 1 3

我的代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 505;

const int inf = 0x3f3f3f3f;

int n,m,s,d;

int map1[maxn][maxn];

bool vis[maxn];

int pre[maxn];

int a,b,len;

int city[maxn];

int cnt[maxn];

int dis[maxn][2];

void dijkstra()
{
	memset(cnt,0,sizeof(cnt));
	memset(vis,0,sizeof(vis));
	memset(dis,0,sizeof(dis));
	
	for(int i=0;i!=n;i++)
	{
		if(map1[s][i])
		{
			dis[i][0]=map1[s][i];
			dis[i][1]=(city[i]+city[s]);
			pre[i]=s;
			cnt[i]++;
		}
		else
		{
			dis[i][0]=inf;
		}
	}
	dis[s][1]=city[s];
	pre[s] = s;
	cnt[s]=1;
	vis[s]=1;
	for(int i=0;i!=n-1;i++)
	{
		int p = 0;
		int mindis=inf,people=0;;
		for(int j=0;j!=n;j++)
		{
			if(!vis[j])
			{
				if(dis[j][0]<mindis||(dis[j][0]==mindis&&dis[j][1]>people))
				{
					mindis = dis[j][0];
					people = dis[j][1];
					p = j;
				}
			}
		}
		
		vis[p]=1;
		for(int j=0;j!=n;j++)
		{
			if(!vis[j])
			{
				if(map1[p][j])
				{
					int td,tp;
					td = dis[p][0]+map1[p][j];
					tp = dis[p][1]+city[j];
					if(td<dis[j][0])
					{
						dis[j][0]=td;
						dis[j][1]=tp;
						pre[j]=p;
						cnt[j]=cnt[p];
					}
					else
					if(td==dis[j][0]&&tp>dis[j][1])
					{
						dis[j][0]=td;
						dis[j][1]=tp;
						pre[j]=p;
						cnt[j]+=cnt[p];
					}
				}
			}
		}
	}
}

void print(int d)
{
	if(d==pre[d])
	{
		printf("%d",d);
	}
	else
	{
		print(pre[d]);
		printf(" %d",d);
	}
}

int main()
{
	freopen("in.txt","r",stdin);
	scanf("%d %d %d %d",&n,&m,&s,&d);
	memset(map1,0,sizeof(map1));
	for(int i=0;i!=n;i++)
	{
		scanf("%d",&city[i]);
		pre[i]=i;
	}
	for(int i=0;i!=m;i++)
	{
		scanf("%d %d %d",&a,&b,&len);
		map1[a][b]=map1[b][a]=len;
	}
	
	dijkstra();
	
	printf("%d %d\n",cnt[d],dis[d][1]);
	
	print(d);
	printf("\n");
	
	return 0;
}

大佬的代码：

#include<bits/stdc++.h>
using namespace std;

const int inf=0x3f3f3f3f;
int n,m,s,d;
int a[505][505],city[505],pre[505],dis[505][2],vis[505],cnt[505];

void dijkstra()
{
	//将初始节点的状态设置好，距离设置为0，已经访问过了，到达自己的最短路径树为1 
    dis[s][0]=0,pre[s]=-1,dis[s][1]=city[s],vis[s]=1,cnt[s]=1;
    while(1)
	{
		//用k保存一个没访问过的距离最近的一个节点的编号，等会儿用来优化路径 
        int Min=inf,k;
        for(int i=0;i<n;++i)
        {
        	if(!vis[i]&&dis[i][0]<Min)
            Min=dis[i][0],k=i;
		}
		//如果发现找到了重点，或者找不到路径了，那就跳出 
        if(k==d||Min==inf) break;
        //将k设为已经访问过了 
        vis[k]=1;
        //使用k对其他没在最短路径集合的点进行优化 
        for(int i=0;i<n;++i)
		{
			//如果没访问过，并且可以优化，那么就优化，并继承上一个节点的最短路径的个数，
			//666，我这里写错了，我没继承 
			//如果到达该点的最短距离更新了，那么就继承现在进的节点
			//如果距离相等，那么就加上当前的节点 
            if(!vis[i]&&dis[i][0]>dis[k][0]+a[k][i])
			{
                dis[i][0]=dis[k][0]+a[k][i];
                dis[i][1]=dis[k][1]+city[i];
                cnt[i]=cnt[k];
                pre[i]=k;
            }
            else if(!vis[i]&&dis[i][0]==dis[k][0]+a[k][i])
			{
                cnt[i]+=cnt[k];
                if(dis[i][1]<dis[k][1]+city[i])
				{
                    dis[i][1]=dis[k][1]+city[i];
                    pre[i]=k;
                }
            }
        }
    }
}

void print(int p)
{
    if(p>=0)
	{
        print(pre[p]);
        if(p==s) printf("%d",p);
        else printf(" %d",p);
    }
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&d);
    //先将所有距离初始化为无穷大 
    for(int i=0;i<n;++i)
    {
    	for(int j=0;j<n;++j)
        {
        	a[i][j]=inf;
		}
	}
        
    for(int i=0;i<n;++i)
    {
    	//输入每个城市的人数，将距离初始化为无穷大，将前驱初始化为-1 
    	scanf("%d",&city[i]),dis[i][0]=inf,pre[i]=-1;
	}
        
    while(m--)
	{
		//初始化地图 
        int t1,t2,t3;
        scanf("%d%d%d",&t1,&t2,&t3);
        a[t1][t2]=a[t2][t1]=t3;
    }
    for(int i=0;i<n;++i)
	{
		//dijkstra 初始化dis数组 
        if(a[s][i]<inf)
            dis[i][0]=a[s][i],dis[i][1]=city[s]+city[i],pre[i]=s,cnt[i]=1;
    }
    dijkstra();
    printf("%d %d\n",cnt[d],dis[d][1]);
    print(d);
    printf("\n");
    return 0;
}