当前位置:网站首页>L2-001 紧急救援 (25 分)
L2-001 紧急救援 (25 分)
2022-07-06 09:14:00 【%xiao Q】
题意:
要求你求出最短路径的数量和最多的救援队的数量,并求S到D的的路径(该路径就是路径最短且召集救援队数量最多的路径)种经过的城市?
分析:
显而易见,这题要用dijkstra算法,不会该算法的可以去学一下,这里的难点在于如何求最短路径的数量和经过的城市,我们可以用三个数组存最短路径的数量,召集救援队的数量,这个点的前驱,然后在更新其它点的时候更新这些数组吗,详情请看代码。
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <unordered_map>
#define LL long long
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define reps(i, a, b) for(int i = a; i < b; i++)
#define pre(i, a, b) for(int i = b; i >= a; i--)
using namespace std;
const int N = 510;
int n, m, s, d;
int g[N][N];
bool st[N];
int cnt[N], number[N]; // 分别用来存救援队的数量和最短路径的数量
int path[N]; // 记录一个点的前驱
int dist[N], w[N];
void dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
cnt[s] = w[s]; //起始点的救援队数量
number[s] = 1; //一开始最短路径为1
// cout << dist[s] << ' ' << cnt[s] << ' ' << number[s] << endl;
rep(i, 1, n)
{
int t = -1;
rep(j, 0, n - 1)
if(!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
st[t] = true;
rep(j, 0, n - 1)
{
if(dist[j] > dist[t] + g[t][j])
{
dist[j] = dist[t] + g[t][j]; //更新最短路径
cnt[j] = cnt[t] + w[j]; //更新救援队的数量
path[j] = t; //记录前驱
number[j] = number[t]; //更新最短路径的数量,因为这里只能从 t->j,即最短路径数量并不会改变
}
else if(dist[j] == dist[t] + g[t][j])
{
if(cnt[j] < cnt[t] + w[j]) // 考虑在路径相等的情况下,救援队的数量
{
cnt[j] = cnt[t] + w[j];
path[j] = t;
}
number[j] += number[t]; //因为是t->j,加上t的最短路径的数量就是j的最短路径的数量
}
}
}
}
int main()
{
cin >> n >> m >> s >> d;
rep(i, 0, n - 1) cin >> w[i];
rep(i, 0, n - 1) path[i] = i;
memset(g, 0x3f, sizeof g);
rep(i, 1, m)
{
int x, y, z;
cin >> x >> y >> z;
g[x][y] = z;
g[y][x] = z;
}
dijkstra();
cout << number[d] << ' ' << cnt[d] << "\n";
vector<int> ans;
int p = d;
while(1) //倒推路径
{
if(p == path[p])
{
ans.push_back(p);
break;
}
ans.push_back(p);
p = path[p];
}
pre(i, 0, ans.size() - 1) //逆序输出
{
if(i != 0) cout << ans[i] << ' ';
else cout << ans[i] << "\n";
}
return 0;
}
边栏推荐
- QT creator create button
- MySQL other hosts cannot connect to the local database
- [number theory] divisor
- 软件测试-面试题分享
- There are three iPhone se 2022 models in the Eurasian Economic Commission database
- Swagger, Yapi interface management service_ SE
- Software testing - interview question sharing
- Image recognition - pyteseract TesseractNotFoundError: tesseract is not installed or it‘s not in your path
- Introduction to the easy copy module
- Remember a company interview question: merge ordered arrays
猜你喜欢
Did you forget to register or load this tag 报错解决方法
Rhcsa certification exam exercise (configured on the first host)
Invalid global search in idea/pychar, etc. (win10)
QT creator design user interface
Picture coloring project - deoldify
Why can't I use the @test annotation after introducing JUnit
Basic use of redis
PyCharm中无法调用numpy,报错ModuleNotFoundError: No module named ‘numpy‘
[recommended by bloggers] C # generate a good-looking QR code (with source code)
[Thesis Writing] how to write function description of jsp online examination system
随机推荐
Windows cannot start the MySQL service (located on the local computer) error 1067 the process terminated unexpectedly
What does usart1 mean
Project practice - background employee information management (add, delete, modify, check, login and exit)
[Thesis Writing] how to write function description of jsp online examination system
La table d'exportation Navicat génère un fichier PDM
项目实战-后台员工信息管理(增删改查登录与退出)
[free setup] asp Net online course selection system design and Implementation (source code +lunwen)
Learning question 1:127.0.0.1 refused our visit
解决:log4j:WARN Please initialize the log4j system properly.
Django运行报错:Error loading MySQLdb module解决方法
Ubuntu 20.04 安装 MySQL
Development of C language standard
SSM整合笔记通俗易懂版
When you open the browser, you will also open mango TV, Tiktok and other websites outside the home page
Ansible实战系列一 _ 入门
Introduction to the easy copy module
JDBC principle
FRP intranet penetration
How to set up voice recognition on the computer with shortcut keys
打开浏览器的同时会在主页外同时打开芒果TV,抖音等网站