当前位置:网站首页>L2-001 emergency rescue (25 points)
L2-001 emergency rescue (25 points)
2022-07-06 11:25:00 【%xiao Q】
The question :
You are required to calculate the number of shortest paths and the number of rescue teams , And ask for S To D The path to success ( This path is the path with the shortest path and the largest number of rescue teams ) Plant the cities you pass ?
analysis :
Obvious , This question uses dijkstra Algorithm , If you don't know the algorithm, you can learn it , The difficulty here is how to find the number of shortest paths and the cities , We can use three arrays to store the number of shortest paths , The number of rescue teams called , Precursor of this point , Then update these arrays when updating other points , See code for details .
#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]; // It is used to store the number of rescue teams and the number of shortest paths
int path[N]; // Record the precursor of a point
int dist[N], w[N];
void dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
cnt[s] = w[s]; // Number of rescue teams at the starting point
number[s] = 1; // At first, the shortest path is 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]; // Update shortest path
cnt[j] = cnt[t] + w[j]; // Update the number of rescue teams
path[j] = t; // Record the precursor
number[j] = number[t]; // Update the number of shortest paths , Because it can only be seen from t->j, That is, the number of shortest paths does not change
}
else if(dist[j] == dist[t] + g[t][j])
{
if(cnt[j] < cnt[t] + w[j]) // Consider the case of equal paths , Number of rescue teams
{
cnt[j] = cnt[t] + w[j];
path[j] = t;
}
number[j] += number[t]; // the reason being that t->j, add t The number of shortest paths is j The number of shortest paths for
}
}
}
}
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) // Backward path
{
if(p == path[p])
{
ans.push_back(p);
break;
}
ans.push_back(p);
p = path[p];
}
pre(i, 0, ans.size() - 1) // Output in reverse order
{
if(i != 0) cout << ans[i] << ' ';
else cout << ans[i] << "\n";
}
return 0;
}
边栏推荐
- Ansible practical Series II_ Getting started with Playbook
- Django running error: error loading mysqldb module solution
- Codeforces Round #753 (Div. 3)
- 牛客Novice月赛40
- [蓝桥杯2021初赛] 砝码称重
- 02 staff information management after the actual project
- Ansible实战系列一 _ 入门
- 报错解决 —— io.UnsupportedOperation: can‘t do nonzero end-relative seeks
- 软件测试与质量学习笔记3--白盒测试
- Asp access Shaoxing tourism graduation design website
猜你喜欢
Django运行报错:Error loading MySQLdb module解决方法
Classes in C #
vs2019 第一个MFC应用程序
Data dictionary in C #
机器学习笔记-Week02-卷积神经网络
Deoldify project problem - omp:error 15:initializing libiomp5md dll,but found libiomp5md. dll already initialized.
Knowledge Q & A based on Apache Jena
自动机器学习框架介绍与使用(flaml、h2o)
Valentine's Day flirting with girls to force a small way, one can learn
vs2019 使用向导生成一个MFC应用程序
随机推荐
Learn winpwn (2) -- GS protection from scratch
What does usart1 mean
Software testing and quality learning notes 3 -- white box testing
MySQL与c语言连接(vs2019版)
About string immutability
Codeforces Round #771 (Div. 2)
软件测试与质量学习笔记3--白盒测试
安装numpy问题总结
使用lambda在循环中传参时,参数总为同一个值
The virtual machine Ping is connected to the host, and the host Ping is not connected to the virtual machine
Database advanced learning notes -- SQL statement
Nanny level problem setting tutorial
Machine learning notes week02 convolutional neural network
AI benchmark V5 ranking
Valentine's Day flirting with girls to force a small way, one can learn
LeetCode #461 汉明距离
[AGC009D]Uninity
保姆级出题教程
报错解决 —— io.UnsupportedOperation: can‘t do nonzero end-relative seeks
When using lambda to pass parameters in a loop, the parameters are always the same value