当前位置:网站首页>Post disaster reconstruction -- Floyd thought
Post disaster reconstruction -- Floyd thought
2022-07-02 10:19:00 【Wawa source】
In the future, you must see the conditions clearly
The time array of this question is not reduced , The query is not reduced , I can't see , Mapping half a day ...
Topic link
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 210,INF=0x3f3f3f3f;
int w[N];
int d[N][N];
int n,m;
signed main()
{
cin>>n>>m;
memset(d,0x3f,sizeof d);
for(int i=0;i<n;i++)cin>>w[i],d[i][i]=0;
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
d[a][b]=d[b][a]=c;
}
int q;
cin>>q;
int pos=0;
while(q--)
{
int x,y,t;
cin>>x>>y>>t;
for(;w[pos]<=t&&pos<n;pos++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
d[i][j]=d[j][i]=min(d[i][j],d[i][pos]+d[pos][j]);
if(w[x]>t||w[y]>t)cout<<-1<<'\n';
else
{
if(d[x][y]>INF/2)cout<<-1<<'\n';
else cout<<d[x][y]<<'\n';
}
}
}
边栏推荐
- This monitoring system makes workers tremble: turnover intention and fishing can be monitored. After the dispute, the product page has 404
- 滲透測試的介紹和防範
- Feature (5): how to organize information
- C language strawberry
- Introduction and prevention of penetration test
- 2837xd code generation - Supplement (3)
- Blender体积雾
- 【避坑指南】Unity3D项目接入腾讯Bugly工具时遇到的坑
- XA Transaction SQL Statements
- 2837xd code generation module learning (2) -- ADC, epwm module, timer0
猜你喜欢
【虚幻】按键开门蓝图笔记
Junit5 supports suite methods
2837xd code generation module learning (3) -- IIC, ECAN, SCI, watchdog, ECAP modules
Sil/pil test of matlab code generation
Remember the use of add method once
webUI自动化学习
测试--面试题总结
Tee command usage example
ue虛幻引擎程序化植物生成器設置——如何快速生成大片森林
Notes de base sur les plans illusoires d'IA (triés en 10 000 mots)
随机推荐
XA Transaction SQL Statements
滲透測試的介紹和防範
Matlab generates DSP program -- official routine learning (6)
Bookmark collection management software suspension reading and data migration between knowledge base and browser bookmarks
[200 Shengxin literatures] 96 joint biomarkers of immune checkpoint inhibitor response in advanced solid tumors
【UE5】AI随机漫游蓝图两种实现方法(角色蓝图、行为树)
Blender摄像机环绕运动、动画渲染、视频合成
Postman--使用
阿里云ack介绍
Zlib download and use
2837xd code generation module learning (2) -- ADC, epwm module, timer0
【虚幻4】UMG组件的简介与使用(更新中...)
The primary market project galaxy will conduct public offering on coinlist on February 17
Configuration programmée du générateur de plantes du moteur illusoire UE - - Comment générer rapidement une grande forêt
Attack and defense world web advanced area unserialize3
Ctrip starts mixed office. How can small and medium-sized enterprises achieve mixed office?
Deep understanding of redis cache avalanche / cache breakdown / cache penetration
Junit4 runs MVN test test suite upgrade scheme
How much is it to develop a system software in Beijing, and what funds are needed to develop the software
2837xd代码生成模块学习(3)——IIC、eCAN、SCI、Watchdog、eCAP模块