题目描述
作为一个城市的应急救援队伍的负责人,你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候,你的任务是带领你的救援队尽快赶往事发地,同时,一路上召集尽可能多的救援队。
输入格式:
输入第一行给出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
算法1
(Dijkstra算法) O(?)
思路:
复习了下y总的视频,其中y总提到一句这个算法是基于贪心的,所以我就想可以在求最短路的同时更新人数
如果路径长度相同,就比较并更新人数
最后输出路径没搞懂,抄的。。。
参考文献
csdn某大哥
我几乎就是抄他的,我虽然能想出大致思路,但图论这块太菜,只知道理论,很多实现不了,这
个人的思路和我的几乎重合,所及来借鉴
原码链接
https://blog.csdn.net/qq_44622401/article/details/104115782
C++ 代码
# include <bits/stdc++.h>
using namespace std;
const int N = 510;
const int INF = 0x3f3f3f3f;
int g[N][N];
int dist[N];
bool st[N];
int n,m,in,out;
int w[N];//存点的权值;(每个城市有几个人)
int num[N];//存最短路的条数
int peo[N];//存人数
int path[N];//存路
void djstl()
{
memset(dist,0x3f,sizeof dist);
dist[in] = 0;//出发地距离为0
num[in] = 1;//初始有一条路
peo[in] = w[in];//初始人为出发城市的人数
for(int i=0;i<n-1;i++)
{
int t = -1;
for(int j=0;j<n;j++)
if(!st[j]&&(t==-1||dist[j]<dist[t]))
t = j;
st[t] = true;
for(int j=0;j<n;j++)
if(dist[t]+g[t][j]<dist[j])
{
dist[j] =dist[t] + g[t][j];//转路先去t再去j
peo[j] = peo[t] + w[j];//j的人等于t的人+j的人
num[j] = num[t];//路的条数没变
path[j] = t;//这条路存下来
}
else if(dist[t]+g[t][j]==dist[j]) //路程相同
{
num[j]+=num[t];//路的条数相加
if(peo[t]+w[j]>peo[j])
{
peo[j] = peo[t] + w[j];
path[j] = t;
//若是j的人比先去t再去j的人少,更新人数和路径
}
}
}
}
void printPath(int v)
{
if(v==in) {printf("%d",v);return ;}
printPath(path[v]);
printf(" %d",v);
return ;
}
int main(void)
{
memset(g,0x3f,sizeof g);
cin >> n >> m >> in >> out;
for(int i = 0;i < n;i++)
cin >> w[i];
while(m--)
{
int a,b,c;
cin >> a >> b >> c;
g[a][b] =c;
g[b][a] = c;
}
djstl();
cout << num[out] << ' ' << peo[out] << endl;
printPath(out);
}