当前位置:网站首页>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';
}
}
}
边栏推荐
- 渗透测试的介绍和防范
- Notes de base sur les plans illusoires d'IA (triés en 10 000 mots)
- 【虚幻】过场动画笔记
- How does {} prevent SQL injection? What is its underlying principle?
- [leetcode] sword finger offer 53 - I. find the number I in the sorted array
- Configuration programmée du générateur de plantes du moteur illusoire UE - - Comment générer rapidement une grande forêt
- Aiphacode is not a substitute for programmers, but a tool for developers
- How to achieve the top progress bar effect in background management projects
- Feature (5): how to organize information
- Project practice, redis cluster technology learning (16)
猜你喜欢

Alibaba cloud SMS service

Beautiful and intelligent, Haval H6 supreme+ makes Yuanxiao travel safer

ESLint 报错

ue虚幻引擎程序化植物生成器设置——如何快速生成大片森林
![[illusory] automatic door blueprint notes](/img/7a/14a66e5b623c7740dc91a15a328b10.png)
[illusory] automatic door blueprint notes
![[illusory] weapon slot: pick up weapons](/img/a7/1e395fc9cdfd0359e7ae4d2313290d.png)
[illusory] weapon slot: pick up weapons

Edge computing accelerates live video scenes: clearer, smoother, and more real-time

Configuration programmée du générateur de plantes du moteur illusoire UE - - Comment générer rapidement une grande forêt

阿里云Prometheus监控服务

【虚幻】过场动画笔记
随机推荐
C language strawberry
[ue5] animation redirection: how to import magic tower characters into the game
Leetcode -- the nearest common ancestor of 236 binary tree
【Visual Studio】每次打开一个Unity3D的脚本,都会自动重新打开一个新的VS2017
Attack and defense world web advanced area unserialize3
Blender体积雾
Centos7 one click compilation and installation of PHP script
Blender model import UE, collision settings
Edge computing accelerates live video scenes: clearer, smoother, and more real-time
[200 Shengxin literatures] 95 multiomics exploration TNBC
Introduction and prevention of penetration test
allure--常用配置项
Minimum number of C language
渗透测试的介绍和防范
Alibaba cloud SMS service
Network real-time video streaming based on OpenCV
Matlab生成dsp程序——官方例程学习(6)
Zlib download and use
Junit4运行mvn test 测试套件升级方案
What is the relationship between realizing page watermarking and mutationobserver?