当前位置:网站首页>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;
//
}
边栏推荐
猜你喜欢
My C language learning records (blue bridge) -- files and file input and output
Linear programming matlab
[Chongqing Guangdong education] higher mathematics I reference materials of Southwest Petroleum University
Communication between microservices
Deeply analyze the chain 2+1 mode, and subvert the traditional thinking of selling goods?
A copy can also produce flowers
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 11
4. File modification
C language - Blue Bridge Cup - promised score
Referenceerror: primordials is not defined error resolution
随机推荐
Fault analysis | analysis of an example of MySQL running out of host memory
Installation and use tutorial of cobaltstrike-4.4-k8 modified version
Data and Introspection__ dict__ Attributes and__ slots__ attribute
Misc (eternal night), the preliminary competition of the innovation practice competition of the National College Students' information security competition
MySQL winter vacation self-study 2022 11 (9)
【若依(ruoyi)】设置主题样式
Apt installation ZABBIX
Elimination games
Gifcam v7.0 minimalist GIF animation recording tool Chinese single file version
Universal crud interface
Is there a completely independent localization database technology
A copy can also produce flowers
Referenceerror: primordials is not defined error resolution
JS events (add, delete) and delegates
I sorted out a classic interview question for my job hopping friends
Redis delete policy
OCR文字识别方法综述
[ruoyi] ztree custom icon (iconskin attribute)
CSP numeric sort
RobotFramework入门(二)appUI自动化之app启动