L2-001 紧急救援（五香连通图输出最短的路径以及最短路径的条数还有最大收益）

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

输入格式:

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

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

输出格式:

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

输入样例1:

4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2

输出样例1:

2 60
0 1 3

输入样例2:（该样例并非是最优解唯一，仅仅用作检测最短路径的条数是否正确）

8 15 0 7
10 10 10 10 10 10 10 10
0 1 1
0 2 1
0 3 1
7 4 1
7 5 1
7 6 1
1 4 1
1 5 1
1 6 1
2 4 1
2 5 1
2 6 1
3 4 1
3 5 1 
3 6 1

输出样例2:

9 40
0 1 4 7

 错误代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
const int N=510;
int p[N][N];
int dist[N];
int dist1[N];
int d[N];
int sum;
int root,mx;
int n,m, s,t1;
int f[N];
bool st[N];
void dfs(int x,int u)
{if(x!=root){dfs(f[x],u+1);}else{cout<<x<<' ';return;}if(u!=1)cout<<x<<' ';elsecout<<x;
}
void dijk()
{memset(dist ,0x3f,sizeof dist);memset(dist1,0,sizeof dist1);dist1[s]=d[s];dist[s]=0;for(int i=1;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]=true;for(int j=0;j<n;j++){if(dist[t]+p[t][j]<dist[j]){f[j]=t;if(j==t1&&dist[t]+p[t][j]<mx)//错误点{mx=dist[t]+p[t][j];sum=1;}dist[j]=dist[t]+p[t][j];dist1[j]=dist1[t]+d[j];}else if(dist[t]+p[t][j]==dist[j]){if(j==t1&&mx==dist[j])sum++;//错误点，仅仅只是看最终达到终点//的最短路径的次数决定了最短路径//的数目，忽略了路径上的其他点的可能遍历次数if(dist1[j]<dist1[t]+d[j]){dist1[j]=dist1[t]+d[j];f[j]=t;}}}}
}
int main()
{cin>>n>>m>>s>>t1;for(int i=0;i<n;i++)cin>>d[i];f[s]=s;mx=0x3f3f3f3f;memset(p,0x3f,sizeof p);while(m--){int a,b,c;cin>>a>>b>>c;p[a][b]=min(p[a][b],c);p[b][a]=p[a][b];}dijk();cout<<sum<<' '<<dist1[t1]<<endl;dfs(t1,1);return 0;
}

样例2下的错误输出：

3 40
0 1 4 7

正确代码 ：

思路（在更新最短距离时用一个数组记录到达一个节点的最短路径个数，如果最短距离被更新，则个数由中间点t的个数值决定，如果最短距离相同，则个数由该点和中间点共同决定）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
const int N=510;
int p[N][N];
int dist[N];
int dist1[N];
int d[N];
int sum;
int root,mx;
int n,m, s,t1;
int f[N];
int cnt[N];
bool st[N];
void dfs(int x,int u)
{if(x!=root){dfs(f[x],u+1);}else{cout<<x<<' ';return;}if(u!=1)cout<<x<<' ';elsecout<<x;
}
void dijk()
{memset(dist ,0x3f,sizeof dist);memset(cnt,0,sizeof cnt);cnt[s]=1;dist1[s]=d[s];dist[s]=0;for(int i=1;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]=true;for(int j=0;j<n;j++){if(dist[t]+p[t][j]<dist[j]){f[j]=t;dist[j]=dist[t]+p[t][j];dist1[j]=dist1[t]+d[j];cnt[j]=cnt[t];}else if (dist[j]==dist[t]+p[t][j]){cnt[j]=cnt[t]+cnt[j];if(dist1[j]<dist1[t]+d[j]){f[j]=t;dist1[j]=dist1[t]+d[j];}}}}
}
int main()
{cin>>n>>m>>s>>t1;for(int i=0;i<n;i++)cin>>d[i];f[s]=s;mx=0x3f3f3f3f;memset(p,0x3f,sizeof p);while(m--){int a,b,c;cin>>a>>b>>c;p[a][b]=min(p[a][b],c);p[b][a]=p[a][b];}dijk();cout<<cnt[t1]<<' '<<dist1[t1]<<endl;dfs(t1,1);return 0;
}