当前位置:网站首页>1003 emergency (25 points), "DIJ deformation"
1003 emergency (25 points), "DIJ deformation"
2022-07-06 02:54:00 【Yang tree Yang tree】
#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define dd double
#define PII pair<int,int>
#define int long long
using namespace std;
const dd eps = 1e-6;
const int mod = 1000003;
const int N = 1e3+10;
int n,m;
int c1,c2;
int cnt[N],sum[N];
int weight[N];
// cnt[j] Deposit is j The number of shortest circuits to the starting point .
// sum[j] Deposit is j The largest number of people on the shortest path to the starting point
/*
n - Number of cities
m - The number of roads
c1 and c2 Cities that must be rescued
*/
//#define int long long
const int INF = 0x3f3f3f3f3f3f3f3f;
int g[N][N], dist[N]; // Dense graphs are stored in adjacency matrices
bool st[N];
void dijkstra()
{
// The starting point is initialized to 0, Other points are initialized to infinity (INF)
memset(dist, 0x3f, sizeof dist);
dist[c1] = 0;
// The starting quantity is 1
cnt[c1]=1;
// Starting number is w1
sum[c1]=weight[c1];
for(int i = 1; i <= n; i++)
{
// Find the point in which the shortest circuit is not currently determined The shortest distance
int t = -1;
for(int j = 0; j < n; j++)
if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
// use t Update other points
for(int j = 0; j < n; j++)
{
if(dist[j]>dist[t]+g[t][j])
{
dist[j]=dist[t]+g[t][j];
cnt[j]=cnt[t];
sum[j]=sum[t]+weight[j];
}
else if(dist[j]==dist[t]+g[t][j])
{
cnt[j]+=cnt[t];
sum[j]=max(sum[j],sum[t]+weight[j]);
}
}
// t The shortest circuit has been determined
st[t] = true;
}
// if INF It means there is no way
}
signed main()
{
// Input part
memset(g,0x3f,sizeof(g));
cin>>n>>m>>c1>>c2;
for(int i=0;i<n;i++)
{
cin>>weight[i];
}
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=min(g[a][b],c);
}
dijkstra();
cout<<cnt[c2]<<" "<<sum[c2]<<endl;
return 0;
//
}
边栏推荐
- Rust language -- iterators and closures
- 原型图设计
- [Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 12
- js 正则过滤和增加富文本中图片前缀
- Codeforces 5 questions par jour (1700 chacune) - jour 6
- Introduction to robotframework (II) app startup of appui automation
- RobotFramework入门(三)WebUI自动化之百度搜索
- [unity3d] GUI control
- Microsoft speech synthesis assistant v1.3 text to speech tool, real speech AI generator
- I sorted out a classic interview question for my job hopping friends
猜你喜欢
[kubernetes series] learn the exposed application of kubernetes service security
Introduction to robotframework (II) app startup of appui automation
Apt installation ZABBIX
QT release exe software and modify exe application icon
主数据管理(MDM)的成熟度
Blue Bridge Cup group B provincial preliminaries first question 2013 (Gauss Diary)
C # create self host webservice
PMP practice once a day | don't get lost in the exam -7.5
CobaltStrike-4.4-K8修改版安装使用教程
Yyds dry inventory comparison of several database storage engines
随机推荐
Follow the mouse's angle and keyboard events
主数据管理(MDM)的成熟度
2.13 simulation summary
XSS challenges绕过防护策略进行 XSS 注入
Li Kou today's question -729 My schedule I
XSS challenges bypass the protection strategy for XSS injection
建模规范:命名规范
[matlab] access of variables and files
Introduction to robotframework (III) Baidu search of webui automation
Introduction to robotframework (I) brief introduction and use
ReferenceError: primordials is not defined错误解决
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 10
深度解析链动2+1模式,颠覆传统卖货思维?
Atcoder beginer contest 233 (a~d) solution
Classic interview question [gem pirate]
How does yyds dry inventory deal with repeated messages in the consumption process?
技术分享 | undo 太大了怎么办
Apt installation ZABBIX
原型图设计
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 22