当前位置:网站首页>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';
}
}
}
边栏推荐
- MySQL -- time zone / connector / driver type
- 虚幻——动画蓝图、状态机制作人物走跑跳动作
- go语言入门
- Blender多鏡頭(多機比特)切換
- Metaclass type and using metaclass to implement model class ORM
- Junit5 supports suite methods
- 2837xd code generation - Supplement (2)
- Notes de base sur les plans illusoires d'IA (triés en 10 000 mots)
- Alibaba cloud SLS log service
- Blender multi lens (multi stand) switching
猜你喜欢

Message mechanism -- getting to know messages and message queues for the first time

2837xd代码生成模块学习(1)——GPIO模块

Junit5 支持suite的方法

Blender模型导入ue、碰撞设置

MySQL index

2837xd code generation module learning (1) -- GPIO module

pytest框架实现前后置

It is the most difficult to teach AI to play iron fist frame by frame. Now arcade game lovers have something

Matlab代码生成之SIL/PIL测试

Blender multi lens (multi stand) switching
随机推荐
Blender multi lens (multi stand) switching
[IDL] Research
Blender多鏡頭(多機比特)切換
[ue5] animation redirection: how to import magic tower characters into the game
Deep understanding of redis cache avalanche / cache breakdown / cache penetration
Blender体积雾
Mysql索引
How to achieve the top progress bar effect in background management projects
阿里云Prometheus监控服务
Message mechanism -- getting to know messages and message queues for the first time
The latest progress and development trend of 2022 intelligent voice technology
Matlab generates DSP program -- official routine learning (6)
【虚幻4】UMG组件的简介与使用(更新中...)
Blender模型导入ue、碰撞设置
[200 Shengxin literatures] 96 joint biomarkers of immune checkpoint inhibitor response in advanced solid tumors
Introduction et prévention des essais de pénétration
Sil/pil test of matlab code generation
【虚幻】过场动画笔记
【Unity3D】无法正确获取RectTransform的属性值导致计算出错
Introduction and Principle notes of UE4 material