题目描述
作为城市的紧急救援团队负责人,你将获得一张你所在国家的特殊地图。
该地图显示了一些通过道路连接的分散城市,道路是双向的。
地图上标出了每个城市的救援队数量以及每对城市之间的每条道路的长度。
当其他城市发出紧急求援信息时,你的工作是尽快带领你的士兵前往该地点,同时,在途中尽可能多地调动救援帮手。
输入格式
第一行包含四个整数 N,表示城市数量(城市编号从 0 到 N−1),M 表示道路数量,C1 表示你当前所在的城市编号,C2 表示发出紧急求援信息的城市编号。
第二行包含 N 个整数,其中第 i 个整数表示城市 i 的救援队数量。
接下来 M 行,每行包含三个整数 c1,c2,Li,表示城市 c1 和城市 c2 之间存在一条道路相连,道路长度为 Li。
数据保证 C1 和 C2 之间至少存在一条路径相连。
输出格式
共一行,两个整数,第一个整数表示 C1 和 C2 之间最短路的数量,第二个整数表示走最短路的情况下,能聚集到的救援队最大数量。
数据范围
2≤N≤500,
1≤M≤600,
1≤Li≤200,
每个城市包含的救援人员数量不超过 200。
样例
输入样例:
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
输出样例:
2 4
算法1
(dijkstra+动态规划) $O(n^2)$
首先是一个裸的dijkstra算法模板
题目中给每一个点上面有一个值,要求求最短路的数量和所有最短路中间权值最大的一条最短路、
dijstra算法中的松弛操作
状态表示:cnt[]数组维护到这个点的最短数量,sum[]数组表示到当前这个点的所有距离的最大值
状态转移:分类讨论的过程,松弛操作无非以下情况需要更新状态
if(dist[j]>dist[t]+g[t][j])
dist[j]=dist[t]+g[t][j];
cnt[j]=cnt[t];
sum[j]=sum[t]+w[j];
if( dist[j]==dist[t]+g[t][j])
cnt[j]+=cnt[t];
sum[j]=max(sum[j],sum[t]+w[j]);
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int g[N][N],dist[N],cnt[N],sum[N];
bool vis[N];
int w[N];
int n,m,c1,c2;
void dijkstra()
{
memset(dist,0x3f,sizeof dist);
dist[c1]=0,cnt[c1]=1,sum[c1]=w[c1];
for(int i=0;i<n;i++)
{
int t=-1;
for(int j=0;j<n;j++)
{
if(!vis[j]&&(t==-1||dist[t]>dist[j]))t=j;
}
vis[t]=true;
for(int j=0;j<n;j++)
{
if(dist[j]>dist[t]+g[t][j])
{
dist[j]=dist[t]+g[t][j];
cnt[j]=cnt[t];
sum[j]=sum[t]+w[j];
}else if( dist[j]==dist[t]+g[t][j])
{
cnt[j]+=cnt[t];
sum[j]=max(sum[j],sum[t]+w[j]);
}
}
}
}
int main()
{
cin>>n>>m>>c1>>c2;
memset(g,0x3f,sizeof g);
for(int i=0;i<n;i++)
{
cin>>w[i];
}
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=min(g[a][b],c);
}
dijkstra();
cout<<cnt[c2]<<" "<<sum[c2];
return 0;
}