L2-001 紧急救援 (25 分)最短路径 迪杰斯特拉算法

题目

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<iostream>
#include<cstring>
using namespace std;
int n,m,c1,c2;
int f[510]; //记录途径那些点
int dist[510],cn[510],sum[510],rshu[510];
int mp[510][510];
bool st[510];
void print(int c2,int c1)
{
	if(c2==c1)
	{
		cout<<c2;//终点就是起点,最后会递归到这一步再开始回溯 
		return ;
	}
	print(f[c2],c1);//f[]最后是最后的点，所以得倒着找点 
	cout<<" "<<c2;
}
void dijkstra()
{
	memset(dist,0x3f,sizeof dist);
	dist[c1]=0,cn[c1]=1,sum[c1]=rshu[c1];//确定起始顶点编号,条数（起点到其本身方式为1），人数 
	for(int i=0;i<n;i++)
	{
		int t=-1;
		for(int j=0;j<n;j++)
		{
			if(!st[j]&&(t==-1||dist[t]>dist[j]))
				t=j;
		}
		st[t]=1;
		for(int j=0;j<n;j++)//确定t后更新各个点的最短路
			//dist[j]=min(dist[j],dist[t]+mp[t][j]);
		{
			if(dist[j]>dist[t]+mp[t][j])
			{
				f[j]=t;//j的上一个点是t
				dist[j]=dist[t]+mp[t][j];
//从起点走到路径j的数量，j的最短路径条数得算上j的前一个点的最短路径条数（方式等于到达前驱的方式） 
				cn[j]=cn[t];
				sum[j]=sum[t]+rshu[j]; 
			}
			else if(dist[j]==dist[t]+mp[t][j])//如果两者最短路一样
			{
				if(sum[j]<sum[t]+rshu[j])
				{
					f[j]=t; // j的上一个点是t
					sum[j]=sum[t]+rshu[j];
				}
				cn[j]=cn[t]+cn[j];//合并路径数量，两种方式距离相等，则方式数相加
				//sum[j]=max(sum[j],sum[t]+rshu[j]); //比较人数，选那个人多的点u
			}
		}
	}
}
int main()
{
	cin>>n>>m>>c1>>c2;
	for(int i=0;i<n;i++)
		cin>>rshu[i];
	memset(mp,0x3f,sizeof mp);
	int x,y,d;
	for(int i=0;i<m;i++)
	{
		cin>>x>>y>>d;
		mp[x][y]=mp[y][x]=min(mp[x][y],d);//无向图对称 不写这个12分
	}
	dijkstra();
	cout<<cn[c2]<<" "<<sum[c2]<<endl;
	print(c2,c1);
	return 0;
}

####洛谷3371 70分 出现MLE：Memory Limit Exceeded，超出内存限制

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,s;
int ju[10010][10010];
int dist[10010];
bool b[10010];
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			ju[i][j]=0x3f3f3f3f;
	//memset(ju,0x3f,sizeof ju);
	while(m--)
	{
		int x,y,w;
		cin>>x>>y>>w;
		//ju[x][y]=w;不对，不能处理重复边的出现  4 2 49  和4 2 214 
		ju[x][y]=min(ju[x][y],w); //如果发生重边的情况则保留最短的一条边
	}
	for(int i=1;i<=n;i++)
		dist[i]=0x3f3f3f3f;
	//memset(dist,0x3f,sizeof dist);会超时 
	dist[s]=0;
	for(int i=1;i<=n;i++)
	{
		int t=-1;
		for(int j=1;j<=n;j++)
			if(b[j]==0&&(t==-1||dist[t]>dist[j]))
				t=j;
		b[t]=1;
		for(int j=1;j<=n;j++)
			dist[j]=min(dist[j],dist[t]+ju[t][j]);
	}
	for(int j=1;j<=n;j++)
	{
		//2^31=2147483648   2^31-1=2147483647
		if(dist[j]==0x3f3f3f3f)
		{
			cout<<2147483647<<" ";
			continue;
		}
		cout<<dist[j]<<" ";
	}
	return 0;
}

####通过代码

#include<iostream>
using namespace std;
long long dis[10100];//防止相加后溢出 
int u[500100],v[500100],w[500100],n,m,s,check;//我们定义一个check，优化用 
const int inf=2147483647;//注意不能是999999999人家要不连通的输出2的31次方-1
int main()
{
	cin>>n>>m>>s;//输入 
	for(int i=1;i<=m;i++)
		cin>>u[i]>>v[i]>>w[i];//读入边 
	for(int i=1;i<=n;i++)
		dis[i]=inf;//dis数组初始化 
	dis[s]=0;
	for(int k=1;k<=n-1;k++)//核心代码：可以解决带负权边的图，外循环循环n-1次n为顶点个数 
	{
		check=0;//check归零 
		for(int i=1;i<=m;i++)//内循环m次m是边的个数，即枚举每一条边 
		{
			//遍历看是否可以通过 u[i]让1号顶点直接到 v[i]的距离变小 
			if(dis[v[i]]>dis[u[i]]+w[i])
			{
				dis[v[i]]=dis[u[i]]+w[i];
				check=1;//如果dis数值改变，check赋值为1 
			}	
		}
		if(check==0)
			break;//如果没变，直接跳出循环，不要浪费时间 
	}
	for(int i=1;i<=n;i++)
		cout<<dis[i]<<" ";//输出 
	return 0;
}