pat甲级打卡-1003 Emergency
2022/4/16 23:42:39
本文主要是介绍pat甲级打卡-1003 Emergency,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 505; int dis[N],w[N]; bool visit[N]; int e[N][N],weight[N],num[N];//num 记录到 i 的最短路径条数 int n,m,c1,c2; const int inf = 99999999; //target 输出最短路径条数,以及最小点权和 int dijkstra(){ memset(dis ,0x3f,sizeof dis); dis[c1] = 0; w[c1] = weight[c1]; num[c1] = 1; for(int i = 0; i < n; i++) { int u = -1, minn = inf; for(int j = 0; j < n; j++) { if(!visit[j] && (u==-1 || dis[j] < dis[u])) { u = j; } } minn=dis[u]; visit[u] = true; for(int v = 0; v < n; v++) { if(visit[v] == false && e[u][v] != inf) { //连接当前最短路上节点,且未被访问 if(dis[u] + e[u][v] < dis[v]) { //更新与当前最短路节点相连的节点的dis最短路径长 dis[v] = dis[u] + e[u][v]; num[v] = num[u];//条数和当前最短路节点一致 w[v] = w[u] + weight[v]; } else if(dis[u] + e[u][v] == dis[v]) { //边权相等 num[v] = num[v] + num[u]; //更新路径数为两种情况的和,一种是走v之前的几条路径,另一种是走过u当前最短路节点的路径条数 if(w[u] + weight[v] > w[v]) //w[]记录到v结点的最大点权和。 w[v] = w[u] + weight[v]; } } } } return num[c2]; } int main(){ memset(e,0x3f,sizeof e); cin>>n>>m>>c1>>c2; for(int i=0;i<n;i++){ cin>>weight[i]; } for(int i=1;i<=m;i++){ int x,y,z; cin>>x>>y>>z; e[x][y]=min(e[x][y],z); e[y][x]=e[x][y]; } cout<<dijkstra()<<" "; //for(int i=0;i<n;i++) cout<<dis[i]<<" "; cout<<w[c2]; return 0; }
这篇关于pat甲级打卡-1003 Emergency的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升