当前位置:网站首页>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';
}
}
}
边栏推荐
- [leetcode] sword finger offer 53 - I. find the number I in the sorted array
- Edge computing accelerates live video scenes: clearer, smoother, and more real-time
- Ctrip starts mixed office. How can small and medium-sized enterprises achieve mixed office?
- Message mechanism -- getting to know messages and message queues for the first time
- Bookmark collection management software suspension reading and data migration between knowledge base and browser bookmarks
- AutoCAD - layer Linetype
- 【避坑指南】使用UGUI遇到的坑:Text组件无法首行缩进两格
- Alibaba cloud SLS log service
- UE4 night lighting notes
- Project practice, redis cluster technology learning (VII)
猜你喜欢
随机推荐
UE illusory engine programmed plant generator setup -- how to quickly generate large forests
UE5——AI追逐(藍圖、行為樹)
Unreal material editor foundation - how to connect a basic material
【虚幻4】从U3D到UE4的转型之路
[ue5] blueprint making simple mine tutorial
ESLint 报错
Project practice, redis cluster technology learning (16)
[ue5] animation redirection: how to import magic tower characters into the game
How does {} prevent SQL injection? What is its underlying principle?
职业规划和发展
Blender石头雕刻
Pycaret | a few lines of code to solve machine learning modeling
[illusory] automatic door blueprint notes
【避坑指南】使用UGUI遇到的坑:Text组件无法首行缩进两格
Alibaba cloud Prometheus monitoring service
【UE5】动画重定向:如何将幻塔人物导入进游戏玩耍
Project practice, redis cluster technology learning (IX)
A model can do two things: image annotation and image reading Q & A. VQA accuracy is close to human level | demo can be played
High level application of SQL statements in MySQL database (II)
What is the relationship between realizing page watermarking and mutationobserver?







