算法
本题在考察朴素版的dijkstra算法同时需要我们对一些信息进行记录。
1.到达某个城市的最短路径数目
2.到达某个城市的最大救援队数目
3.由起点到终点,在距离尽可能短和救援队数目尽可能多的情况下的路径
上述的三种信息可以在更新距离时进行记录,其中需要注意MinPathNum[start] = 1,MaxGroup[start] = city[start]
,
(start为起点的意思,其他也为字面意思)输出路径采用递归输出即可。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n,m,s,d;
int city[N];
int g[N][N];
int dist[N],path[N],cnt[N],group[N];
bool st[N];
void dijkstra()
{
memset(dist,0x3f,sizeof(dist));
dist[s] = 0;
group[s] = city[s];
cnt[s] = 1;
for(int i=0;i<n;i++)
{
int tmin = 99999999,id = 0;
for(int j=0;j<n;j++)
if(!st[j]&&dist[j]<tmin)
id = j,tmin = dist[j];
st[id] = true;
for(int j=0;j<n;j++)
if(g[id][j]!=0x3f3f3f3f)
{
if(dist[j]>dist[id]+g[id][j])
{
dist[j] = dist[id] + g[id][j];
path[j] = id;
cnt[j] = cnt[id];
group[j] = group[id] + city[j];
}
else if(dist[j]==dist[id]+g[id][j])
{
cnt[j] += cnt[id];
if(group[j]<group[id]+city[j])
{
group[j] = group[id] + city[j];
path[j] = id;
}
}
}
}
}
void printPath(int u)
{
if(u==s)
{
cout<<u;
return ;
}
printPath(path[u]);
cout<<" "<<u;
return ;
}
int main()
{
cin>>n>>m>>s>>d;
memset(g,0x3f,sizeof(g));
for(int i=0;i<n;i++) cin>>city[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[d]<<" "<<group[d]<<endl;
printPath(d);
return 0;
}