pta l2-1紧急救援(Dijkstra)
2024-08-26 04:56:41
题目链接:https://pintia.cn/problem-sets/994805046380707840/problems/994805073643683840
题意:给n个城市,m条边,每个城市有一定数量的救援队,起点s,终点d,求s到d的最短距离,同时路上尽可能召集更多的救援队。
思路:单元最短路径问题,用dijkstra算法,需要增加一维表示救援队的数量,还有就是题目要求输出最短路径的条数,用ct数组来表示,另外用pre数组表示路径中的上一个结点,用来回溯路径并打印。
AC代码:
#include<bits/stdc++.h>
using namespace std; const int inf=0x3f3f3f3f;
int n,m,s,d;
int a[][],jyd[],pre[],dis[],num[],vis[],ct[]; void dijkstra(){
dis[s]=,pre[s]=-,num[s]=jyd[s],vis[s]=,ct[s]=;
while(){
int Min=inf,k;
for(int i=;i<n;++i)
if(!vis[i]&&dis[i]<Min)
Min=dis[i],k=i;
if(k==d||Min==inf) break;
vis[k]=;
for(int i=;i<n;++i){
if(!vis[i]&&dis[i]>dis[k]+a[k][i]){
dis[i]=dis[k]+a[k][i];
num[i]=num[k]+jyd[i];
ct[i]=ct[k];
pre[i]=k;
}
else if(!vis[i]&&dis[i]==dis[k]+a[k][i]){
ct[i]+=ct[k];
if(num[i]<num[k]+jyd[i]){
num[i]=num[k]+jyd[i];
pre[i]=k;
}
}
}
}
} void print(int p){
if(p>=){
print(pre[p]);
if(p==s) printf("%d",p);
else printf(" %d",p);
}
} int main(){
scanf("%d%d%d%d",&n,&m,&s,&d);
for(int i=;i<n;++i)
for(int j=;j<n;++j)
a[i][j]=inf;
for(int i=;i<n;++i)
scanf("%d",&jyd[i]),dis[i]=inf,pre[i]=-;
while(m--){
int t1,t2,t3;
scanf("%d%d%d",&t1,&t2,&t3);
a[t1][t2]=a[t2][t1]=t3;
}
for(int i=;i<n;++i){
if(a[s][i]<inf)
dis[i]=a[s][i],num[i]=jyd[s]+jyd[i],pre[i]=s,ct[i]=;
}
dijkstra();
printf("%d %d\n",ct[d],num[d]);
print(d);
printf("\n");
return ;
}
最新文章
- [LintCode] Longest Increasing Subsequence 最长递增子序列
- JavaWeb---总结(十五)JSP基础语法
- idea使用心得(1)-快捷键用法
- Virtualbox网络设置和无UI启动
- Action的执行
- Discuz!NT静态文件缓存(SQUID)
- Dede 列表页 缩略图 有显示无则不显示
- SpriteKit游戏开发
- 修改spfile导致oracle无法启动
- linux入门之用户管理
- HDU 2203 亲和串(KMP)
- [国嵌攻略][097][U-Boot新手入门]
- MySql实现sequence功能的代码
- label 和input/textarea居中对齐
- 推荐一些socket工具,TCP、UDP调试、抓包工具
- LintCode #3 统计数字
- 关于消息队列的使用----ActiveMQ,RabbitMQ,ZeroMQ,Kafka,MetaMQ,RocketMQ
- 【数组】Search for a Range
- XMPPFramework核心类介绍
- Cheatsheet: 2017 10.01 ~ 12.31