L2-001 紧急救援 (25 point(s))

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

/*
dijkstra O(n^2+m) +O(n)
求出S->D的所有最短路,统计数目,统计权值和
输出最短路数目和最大权值和即可 
两种写法,邻接矩阵邻接表 
*/
const int N=510;
int g[N][N],w[N],dis[N];;//路径长度和权值 
int cnt[N];//最短路的条数 
bool st[N];//每个点的最短路是否已经确定。 
int n,m,s,d,sum[N];
int pre[N];//记录每个节点的前驱 

void dfs(int s,int d)//打印从s->d的路径 
{
	if(s==d)
	{
		cout<<s;return ;
	}
	dfs(s,pre[d]);
	printf(" %d",d);
}

void dijkstra(int s,int d)
{
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;
	cnt[s]=1;
	sum[s]=w[s];
	for(int i=0;i<n;i++)
	{
		int t=-1;
		for(int j=0;j<n;j++)
		{
			if(!st[j]&&(t==-1||dis[t]>dis[j]))//dijkstra板子都能搞错！
				t=j;
		}
		
		for(int j=0;j<n;j++)
		{
			if(dis[j]>dis[t]+g[t][j])
			{
				dis[j]=dis[t]+g[t][j];
				sum[j]=w[j]+sum[t];
				cnt[j]=cnt[t];
				pre[j]=t;
			}
			else if(dis[j]==dis[t]+g[t][j])
			{
				if(sum[j]<w[j]+sum[t])
				{
				    sum[j]=w[j]+sum[t];pre[j]=t;
				}
				cnt[j]+=cnt[t];
			}
		}
		st[t]=1;
	}
	
	cout<<cnt[d]<<" "<<sum[d]<<endl;
	dfs(s,d);
}

int main()
{
	cin>>n>>m>>s>>d;
	memset(g,0x3f,sizeof g);
	for(int i=0;i<n;i++)
	{
		cin>>w[i];
	}
	for(int i=0;i<m;i++)
	{
		int a,b,c;cin>>a>>b>>c;
		g[a][b]=g[b][a]=min(g[a][b],c);
	}
	dijkstra(s,d);
	return 0;
}