推荐成都网站建设,四川seo推广方案,北京网站设计公司新鸿儒,佛山外贸网站建设流程L2-001 紧急救援
分数 25
作为一个城市的应急救援队伍的负责人#xff0c;你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候你的任务是带领你的救援队尽快赶往事发地同时一路上召集尽可能多的救援队。
输入格式:
输入第一行给出4个正整数N、M、S、D其中N2≤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
题解
根据题意很容易想到这是要用最短路算法但求的不是最短路径而是最短路的数目和一堆奇奇怪怪的东西。
最短路的数目可以在判断最短路的时候就加上去详见洛谷P1144最短路计数。
题目还要求在路径最短的同时还要救援队最多那么在遇到两个同样长的路径时判断哪条路的救援队加起来更多以此作为判断依据来更新路径。
最后记录一整条路径输出就好了。
#includebits/stdc.h
using namespace std;
#define ll long long
const int inf1e9;
const int N505;
ll n,m,s,d;
ll dis[N],vis[N];//dis是起点到i点的最短路径
ll jy[N];
ll ms[N];//最短路径条数
ll maxjy[N];//没用上
ll fa[N];//记录该点的父节点
ll ans[N];//当前点最多的救援队数量
ll sum;
vectorpairint,int g[N];//用vector存图
vectorll path;//存放路径
ll out[N];
//迪杰斯特拉算法
void Dij(ll s)
{for(int i0;in;i){dis[i]inf;}dis[s]0;priority_queuepairll,int q;for(int i0;in;i){q.push(make_pair(-dis[i],i));}while(!q.empty()){int uq.top().second;q.pop();if(vis[u]1) continue;vis[u]1;for(int i0;ig[u].size();i){int vg[u][i].first;int wg[u][i].second;if(dis[v]dis[u]w)//是最短路就更新{dis[v]dis[u]w;ms[v]ms[u];fa[v]u;ans[v]ans[u]jy[v];q.push(make_pair(-dis[v],v));}else if(dis[v]dis[u]w)//遇到同样短的路{ms[v]ms[u];if(ans[v]ans[u]jy[v])//判断谁的救援队多{fa[v]u;//更新ans[v]ans[u]jy[v];}}}}
}
//记录路径
void getPath(ll s,ll d)
{path.push_back(d);while(d!s){dfa[d];path.push_back(d);}reverse(path.begin(),path.end());int i0;for(auto k:path){i;out[i]k;}
}
int main()
{cinnmsd;for(int i0;in;i){cinjy[i];}while(m--){int x,y,w;cinxyw;//双向存图g[x].push_back(make_pair(y,w));g[y].push_back(make_pair(x,w));}//初始化ms[s]1;ans[s]jy[s];Dij(s);getPath(s,d);//输出coutms[d] ;coutans[d]endl;for(int i1;ipath.size()-1;i){coutout[i] ;}coutout[path.size()]endl;return 0;
}
